Re: [Ocaml-reins-devel] Fedora - Several questions

[Michael F. <fu...@cs...>]

On Wed, 3 Sep 2008, Richard W.M. Jones wrote:

> I made a Fedora package.  The tracking bug for review and inclusion is
> here:
>
>  https://bugzilla.redhat.com/show_bug.cgi?id=460732

Great, thanks!

> I have several questions related to this:
>
> (1) Current, first and only version is '0.1a'.  The 'a' is a problem
> for Fedora because it's ambiguous whether the next version could be
> '0.1b' or '0.1'.  Ideally it'd be good if the next version was '0.2'
> and we could just drop these letters altogether :-)  What will the next
> verison be?

The very first version was 0.1.  I released 0.1a just hours later to 
clarify the license.  The next release will be 0.2 and I plan to stick to 
numeric releases as a general convention.

> (2) When is the next release likely?  Are there outstanding patches
> queued up for reins?  (I don't see much activity on the mailing list).

It's been a little while since I've touched the codebase and have been 
wanting to get back to it lately.  There are quite a few changes in svn 
that are not part of a released version (perhaps most importantly to a 
package maintainer, the installation target is broken in 0.1a).  Let me 
take a day or two to re-evaluate where the code lies in terms of making a 
release.  I don't think there many things that I need to do, so hopefully 
I can make a release sometime this weekend.

> (3) I frequently need a structure called a Segment Tree to represent
> ranges of memory addresses with holes.  (Or rather, I need to
> represent ranges of memory addresses with holes, and for that I've
> implemented a Segment Tree).

       <--- range1 --->             <--- range2 --->
                                             <--- range3 --->
   |   |              |             |        |              |        |
   0  100            200           300      350            450      500

   Operations:
   (i) Fast map from address to byte in range at address or hole.
   (ii) Fast searches.
   (iii) If a new range overlaps an old one, then it obscures the old
     range at overlapping addresses.  (This is currently a slow operation
     because we rebuild the segment tree).

I don't quite understand the difference between (i) and (ii).  I guess 
that for (i), you want to be able to map a value to range (e.g., looking 
up 150 would give "range1")?  For (ii), is this operation meant to test if 
a range is already present in the tree?

I don't have any experience working with segment trees, but after just 
reading the article on wikipedia, there appear to be some techniques that 
help with (iii).  In particular, adding new intervals can be done in O(log 
N) time where you seem to imply yours is O(n)?  (And in fact, augmented 
segment trees seem pretty straightforward to implement).

> I don't see anything suitable in Reins which can be used to implement
> this, but then I'm not familiar with all of the structures -- could
> one be used to implement this?

I don't believe any existing structures could be used directly to 
implement segment trees.  It sounds like they would make an excellent 
addition to Reins :-)

> Now this implementation isn't suitable for inclusion in Reins at the
> moment.  The particular problems with it are as far as I'm concerned:
>
> (a) Over-complex yet rather inflexible.

I didn't look at your code too deeply, so I don't fully understand what 
you are referring to (given the coupling of the underlying segment tree vs 
the memory map that you implemented on top of it), but it seems like it is 
a good start.  For example, the effectful phantom types don't seem 
necessary for the underlying data structure, but are used to guard 
accesses to the underlying data?

> (b) Needs to work with an unsigned int64 range, but currently the
>   range is signed so it breaks with addresses > 0x7fffffff_ffffffff.

Most of the data structures in Reins are functors over the underlying 
datatypes used in the containers, so it would be nice to be able to follow 
this convention.  I don't know what tradeoffs there would be, but 
supporting intervals over any (totally ordered) data would be great. 
However, if this is too impractical, Reins also includes the Integral 
module signature (used by Int, Int32, Int64, etc...) which support 
arithmetic operations which could be another option.

> (c) Includes C code, which is really necessary for getting the kind of
>   speed we require from searches.

I do have a rather strong preference to not include any C code in the 
library.  Out of curiousity, how much faster is your C version than the 
corresponding OCaml version? (I'm guessing memmem could be a rather large 
win?)

> On the other hand, it is persistent ...
:-D

> So, any comments on whether I can either reimplement this in terms of
> another Reins structure, or if a properly functorized segment tree is
> a good candidate for inclusion in Reins?

I would love to include a functorized version of your segment tree 
implementation in the library.  It would be nice if it included the same 
operations as the other containers (iter, fold, union, compare, to_string, 
gen, etc..), but if you supplied a core implementation I could certainly 
help with the implementation of this auxiliary functions.

Cheers,
-Mike