Re: [boost] Re: new component, extent_set<>

From: Nathan Myers (ncm-yahoospam_at_[hidden])
Date: 2001-12-29 15:59:06

"joel de guzman" wrote:
> From: "Nathan Myers" :
> > 
> > A bit set implementation (sparse or otherwise) wouldn't be useful in my
> > application.  It will be easy to add general set operations to extent_set 
> > if anybody finds them valuable; in my application the greater efficiency 
> > of the more-restricted interface matters, and the preconditions matter not 
> > at all.
> 
> The sparse bit set implemented as range-runs is a superset of
> the extent set. Internally it's almost alike. I haven't checked but 
> performance wise, the extent set shouldn't be much faster than
> the range-run in the average case especially if you are not inserting
> or removing overlapping ranges anyway. I haven't done some profiling
> though and perhaps I am wrong.

Now that I have had an opportunity to read Joel's code, I can comment
further.  BTW, it was not where he said, but here instead:
  http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/spirit/spirit/boost/spirit/impl/chset.ipp

Joel's implementation special-cases char, signed char, and unsigned char,
and uses a bitmap representation for them.  For others, it uses a sorted
vector of ranges, rather than a map indexed on the first element.  As a 
result, insert and erase operations involve block moves, but memory usage
is tight, where in extent_set<> everything involves tree operations.  
Joel's uses reference counting, with copy-on-write to enable efficient
copy/assignment.

The important differences are more subtle.  Joel's interface emphasizes
construction, copying, combining and membership tests; extent_set<>
emphasizes inserting and erasing ranges, and scanning the ranges present.  
These differences are appropriate to their usage domains; Joel's for
representing character class membership, extent_set<> for resource 
allocation.  Joel's is a higher-level structure that could easily use
extent_set<> in its implementation, given a few more operators.

Along another dimension, Joel's uses native operators (e.g. less than)
where mine is parameterized on these operations like std::map<> itself.

I don't think we should let similarities in implementation details 
distract us from what a component is for, and how well it serves that 
purpose.  Joel's design is highly evolved to be useful to aid parsing.
My extent_set<> is more primitive, in the zoological sense, and 
lower-level, and potentially more generally applicable as it matures.

Nathan Myers
ncm at cantrip dot org