Performance fix: Check half-closed descriptors at most once per second.
A few revisions back, comm checked half-closed descriptors once per
second, but the code was buggy. I replaced it with a simpler code that
checked each half-closed descriptor whenever the OS would mark it as
ready for reading. That was a bad idea: The checks wasted a lot of CPU
cycles because half-closed descriptors are usually ready for reading all
the time.
This revision resurrects 1 check/sec limit, but hopefully with fewer
bugs. In my limited tests, CPU usage seems to be back to normal.
Added a DescriptorSet class to manage an unordered collection of unique
descriptors. The class might be useful for deferred reads as well, but
that remains to be seen.
The DescriptorSet class has O(1) complexity for search, insertion,
and deletion. It uses about 2*sizeof(int)*MaxFD bytes. Splay tree that
used to store half-closed descriptors previously uses less RAM for small
number of descriptors but has O(log n) complexity.
The DescriptorSet code should probably get its own .h and .cc files,
especially if it is going to be used by deferred reads.
Thank you,
Alex.
Performance fix: Check half-closed descriptors at most once per second.
A few revisions back, comm checked half-closed descriptors once per second,
but the code was buggy. I replaced it with a simpler code that checked each
half-closed descriptor whenever the OS would mark it as ready for reading.
That was a bad idea: The checks wasted a lot of CPU cycles because half-closed
descriptors are usually ready for reading all the time.
This revision resurrects 1 check/sec limit, but hopefully with fewer bugs. In
my limited tests CPU usage seems to be back to normal.
Added a DescriptorSet class to manage an unordered collection of unique
descriptors. The class might be useful for deferred reads as well, but that
remains to be seen.
The DescriptorSet class has O(1) complexity for search, insertion,
and deletion. It uses about 2*sizeof(int)*MaxFD bytes. Splay tree that used to
store half-closed descriptors previously uses less RAM for small number of
descriptors but has O(log n) complexity.
=== modified file 'src/comm.cc'
--- src/comm.cc 2008-09-22 21:56:44 +
+++ src/comm.cc 2008-09-24 23:09:33 +
@@ -224,6 +224,144 @@
CBDATA_CLASS(ConnectStateData);
};
+/// an unordered collection of unique descriptors with O(1) complexity
+class DescriptorSet {
+// \todo: Should we use std::setint with its flexibility? Our implementation
+// has constant overhead, which is smaller than log(n) of std::set.
+public:
+// for STL compatibility, should we decide to switch to std::set or similar
+typedef const int *const_iterator;
+
+DescriptorSet();
+~DescriptorSet();
+
+/// checks whether fd is in the set
+bool has(const int fd) const { return 0 = fd fd capacity_
+index_[fd] = 0; }
+
+bool add(int fd); /// adds if unique; returns true if added
+bool del(int fd); /// deletes if there; returns true if deleted
+int pop(); /// deletes and returns one descriptor, in unspecified order
+
+bool empty() const { return !size_; } /// number of descriptors in the set
+
+/// begin iterator a la STL; may become invalid if the object is modified
+const_iterator begin() const { return descriptors_; }
+/// end iterator a la STL; may become invalid if the object is modified
+const_iterator end() const { return begin() + size_; }
+
+void print(std::ostream os) const;
+
+private:
+// these would be easy to support when needed; prohibit for now
+DescriptorSet(const DescriptorSet s); // declared but undefined
+DescriptorSet operator =(const DescriptorSet s); // declared, undefined
+
+int *descriptors_; /// descriptor values in random order
+int *index_; /// descriptor:position index into descriptors_
+int capacity_; /// number of available descriptor slots
+int size_; /// number of descriptors in the set
+};
+
+inline std::ostream
+operator (std::ostream os, const DescriptorSet ds)
+{
+ds.print(os);
+return os;
+}
+
+static DescriptorSet *TheHalfClosed = NULL; /// the set of half-closed FDs
+static bool WillCheckHalfClosed = false; /// true if check is scheduled
+static EVH commHalfClosedCheck;
+static void commPlanHalfClosedCheck();
+
+DescriptorSet::DescriptorSet(): descriptors_(NULL), index_(NULL),
+capacity_(0), size_(0)
+{
+// we allocate once and never realloc, at least for now
+capacity_ = Squid_MaxFD;
+descriptors_ = new int[capacity_];
+index_ = new int[capacity_];
+
+// fill index with -1s to be able to say whether a descriptor is present
+// it is not essential to fill the descriptors, but it enables more checks
+for (int i = 0; i capacity_; ++i)
+index_[i] = descriptors_[i] = -1;
+}
+
+DescriptorSet::~DescriptorSet()
+{
+delete[] descriptors_;
+delete[] index_;
+}
+
+/// adds if unique; returns true if added
+bool
+DescriptorSet::add(int fd)
