ocaml-reins-devel — Discussion list for ocaml-reins development

Re: [Ocaml-reins-devel] Godi package?

[David T. <Dav...@un...>]

Thanks! We'll try and add Reins to release 0.2.

Cheers,
 David

On Mon, 2008-09-08 at 15:31 -0400, Michael Furr wrote:
> >> From what I gathered, Reins has Debian and Fedora packages but none for
> > Godi. Could you please consider contributing a Godi package, too? It's a
> > simple task.
> 
> Sure, I can certainly do that. I'll work on it later this week, probably 
> as part of a new release.
> 
> -m

-- 
David Teller-Rajchenbach
 Security of Distributed Systems
  http://www.univ-orleans.fr/lifo/Members/David.Teller
 Angry researcher: French Universities need reforms, but the LRU act brings liquidations. 

Re: [Ocaml-reins-devel] Godi package?

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

On Mon, 8 Sep 2008, David Teller wrote:

> We're interested in adding Reins to Batteries Included, an on-going 
> effort to create a comprehensive OCaml standard platform from existing 
> open-source projects. However, we attempt to pick only projects which 
> have packages for Debian, Fedora and Godi.
>
>> From what I gathered, Reins has Debian and Fedora packages but none for
> Godi. Could you please consider contributing a Godi package, too? It's a
> simple task.

Sure, I can certainly do that. I'll work on it later this week, probably 
as part of a new release.

-m

[Ocaml-reins-devel] Godi package?

[David T. <Dav...@un...>]

     Hi everyone,

 We're interested in adding Reins to Batteries Included, an on-going
effort to create a comprehensive OCaml standard platform from existing
open-source projects. However, we attempt to pick only projects which
have packages for Debian, Fedora and Godi. 

>From what I gathered, Reins has Debian and Fedora packages but none for
Godi. Could you please consider contributing a Godi package, too? It's a
simple task.

Thanks,
 David
-- 
David Teller-Rajchenbach
 Security of Distributed Systems
  http://www.univ-orleans.fr/lifo/Members/David.Teller
 Angry researcher: French Universities need reforms, but the LRU act brings liquidations. 

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

[Richard W.M. J. <rj...@re...>]

On Wed, Sep 03, 2008 at 04:45:31PM -0400, Michael Furr wrote:
> On Wed, 3 Sep 2008, Richard W.M. Jones wrote:
> > (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.

Thanks for the clarifications.

Reins has in fact just been approved for Fedora, so will be added
within a matter of days.

  https://bugzilla.redhat.com/show_bug.cgi?id=460732

> > (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?

No (ii) is completely different from that.  The purpose of using the
structure is so that we can search for binary strings within the
memory map, and we need to do this very rapidly, because kernel images
are very large.  So we offer some search primitives that allow you to
quickly look for fixed binary strings within ranges, skipping holes.

> 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).

The overlapping case isn't actually that important.  We don't use this
case in practice, although my implementation mostly does the right
thing.

However it turns out that adding new ranges is much more common than I
initially expected, and at the moment my implementation rebuilds the
segment tree from scratch each time, which isn't good.  Again in
practice this doesn't seem to matter that much since the time is
dominated by searches, not by rebuilding the segment tree.  But in a
general purpose structure it'd be nice if we didn't have to completely
rebuild it each time.

> > (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?

Yes, it's all a bit mixed up.

> > (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.
> 
> > 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.

I'll have a look at doing it, but probably not soon.

Rich.

-- 
Richard Jones, Emerging Technologies, Red Hat  http://et.redhat.com/~rjones
virt-top is 'top' for virtual machines.  Tiny program with many
powerful monitoring features, net stats, disk stats, logging, etc.
http://et.redhat.com/~rjones/virt-top

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

[Richard W.M. J. <rj...@re...>]

On Wed, Sep 03, 2008 at 04:45:31PM -0400, Michael Furr wrote:
> > (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?)

I'll try to answer the rest tomorrow, but this caught my eye.  The
answer is that the C call to memmem made the difference between this
being practical and unusable.  I don't recall the precise numbers but
it was something like 45+ second search time down to a second.

Hopefully the search function can be functorized too which means it
won't need to appear in the Reins code.  (Although myself I have no
objection to including little bits of C in things providing that it
doesn't affect portability.)

Rich.

-- 
Richard Jones, Emerging Technologies, Red Hat  http://et.redhat.com/~rjones
virt-df lists disk usage of guests without needing to install any
software inside the virtual machine.  Supports Linux and Windows.
http://et.redhat.com/~rjones/virt-df/

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

[Ocaml-reins-devel] Fedora - Several questions

[Richard W.M. J. <rj...@re...>]

I made a Fedora package.  The tracking bug for review and inclusion is
here:

  https://bugzilla.redhat.com/show_bug.cgi?id=460732

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?

(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).

(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 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?

If not, then I offer this implementation:
  http://et.redhat.com/~rjones/virt-mem/html/Virt_mem_mmap.html
  http://hg.et.redhat.com/virt/applications/virt-mem--devel/?f=83a8b07174fd;file=lib/virt_mem_mmap.ml
  http://hg.et.redhat.com/virt/applications/virt-mem--devel/?f=265dfb7410c9;file=lib/virt_mem_mmap.mli
  http://hg.et.redhat.com/virt/applications/virt-mem--devel/?f=51c08794adc0;file=lib/virt_mem_mmap_c.c

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.
 (b) Needs to work with an unsigned int64 range, but currently the
   range is signed so it breaks with addresses > 0x7fffffff_ffffffff.
 (c) Includes C code, which is really necessary for getting the kind of
   speed we require from searches.

On the other hand, it is persistent ...

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?

Rich.

-- 
Richard Jones, Emerging Technologies, Red Hat  http://et.redhat.com/~rjones
virt-top is 'top' for virtual machines.  Tiny program with many
powerful monitoring features, net stats, disk stats, logging, etc.
http://et.redhat.com/~rjones/virt-top

[Ocaml-reins-devel] AVL trees

[Ashish A. <aga...@gm...>]

I notice there are no tree data structures included in Reins, although trees
are used internally to represent other data structures. For example, AVLSet
and AVLMap have all the operations required to implement an AVL tree. Is
there any particular reason the tree operations have not been factored out?
I ask because I need an AVL tree to implement a different kind of set.

Re: [Ocaml-reins-devel] loading Reins

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

On Fri, 18 Apr 2008, Ashish Agarwal wrote:

> I just re-installed my OCaml system with Godi, and was trying again to use
> Reins. Unfortunately, I cannot seem to get things working. Does anyone know
> if this is an installation issue, or am I just doing things wrong (I'm new
> to godi and findlib). Thanks for any help.

The current released tarball has a broken installation target.  You need 
to copy the file "reins.cmi" to the same place as "reins.cma" and it 
should work (or alternatively, just use the svn sources which also include 
a few other bugfixes).

-Mike

[Ocaml-reins-devel] loading Reins

[Ashish A. <aga...@gm...>]

I just re-installed my OCaml system with Godi, and was trying again to use
Reins. Unfortunately, I cannot seem to get things working. Does anyone know
if this is an installation issue, or am I just doing things wrong (I'm new
to godi and findlib). Thanks for any help.

# #use "topfind";;
- : unit = ()
Findlib has been successfully loaded. Additional directives:
  #require "package";;      to load a package
  #list;;                   to list the available packages
  #camlp4o;;                to load camlp4 (standard syntax)
  #camlp4r;;                to load camlp4 (revised syntax)
  #predicates "p,q,...";;   to set these predicates
  Topfind.reset();;         to force that packages will be reloaded
  #thread;;                 to enable threads

- : unit = ()
# #load "unix.cma";;
# #load "nums.cma";;
# #require "reins";;
/Users/ashish/godi/lib/ocaml/site-lib/reins: added to search path
/Users/ashish/godi/lib/ocaml/site-lib/reins/reins.cma: loaded
# open Reins;;
Unbound module Reins

I also tried loading the cma file directly:

# #load "/Users/ashish/godi/lib/ocaml/site-lib/reins/reins.cma";;
# open Reins;;
Unbound module Reins

Re: [Ocaml-reins-devel] Feature request: map2 function for DoubleQueue

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

On Mon, 10 Dec 2007, Charles Buchinski wrote:

> Hello.
Hi!

> I'd like to request that in the DoubleQueue module, a map2 function be
> added, analogous to the function by the same name in OCaml's standard
> List library.  It probably makes sense to implement the rest of the
> "iterators on two lists" equivalents for DoubleQueues as well, but
> personally speaking, the map2 function would be most useful.

Thanks for the message, it's helpful to hear what people miss from the 
library.  I do have on my todo list to implement the rest of the functions 
from the standard library List (and the Set and Map) module.  I'll be sure 
to do map2 soon!

Cheers,
-Mike

[Ocaml-reins-devel] Feature request: map2 function for DoubleQueue

[Charles B. <ch...@ya...>]

Hello.

I'd like to request that in the DoubleQueue module, a map2 function be
added, analogous to the function by the same name in OCaml's standard
List library.  It probably makes sense to implement the rest of the
"iterators on two lists" equivalents for DoubleQueues as well, but
personally speaking, the map2 function would be most useful.

Thanks!



      ____________________________________________________________________________________
Be a better friend, newshound, and 
know-it-all with Yahoo! Mobile.  Try it now.  http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ 

Re: [Ocaml-reins-devel] possible bugs in iterators

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

On Mon, 5 Nov 2007, Ashish Agarwal wrote:

> Hi. Please consider following code:
[snip]

> which prints out
>  1 2 3 4

Oops!

> What is the semantics of Traverse_While? I was expecting the iterator to
> stop at 3.

Indeed, this is the intended semantics.

> The iterator seems to go one element extra. Trying with m = 0 prints the 
> value 1 even though the predicate given to Traverse_While is never 
> satisfied.
>
> Also, leave m = 3, and remove 2 from the list. Then we get Exception:
> Failure "get_value".
> Alternatively, leave the list as shown above and set m = 7. I was expecting
> same error again, but there is no Failure this time.

Hmm... sorry about that.  I must admit I haven't actually tested the While 
iterator as much as I should.  I wasn't sure if I liked the way the cursor 
interface was setup, so I've actually been planning on revisiting this 
entire part of the library.  I'm currently insanely busy working on a 
paper, but I'll look at this next week when I should (finally) have some 
time to get back to hacking on reins.

Thanks for your email.
-m

P.S.  If you have any suggestions about how to improve the way the 
iterators or cursors are presented, I would love to hear them.  I have 
only 1 or 2 usage scenerios in my head and I'm not sure how other people 
might like to use these.

[Ocaml-reins-devel] possible bugs in iterators

[Ashish A. <aga...@gm...>]

Hi. Please consider following code:

----------
module Set = Reins.AVLSet.MonoSet(Reins.Types.Int)
module Iter = Reins.TreeSetIterator.Make(Set)

let l = [3;5;2;7;4;8;1]
let s = List.fold_left (fun s v -> Set.add v s) Set.empty l
let dir = Iter.Ascending Iter.InOrder
let m = 3
let trav = Iter.Traverse_While (fun n -> n <= m)
let iter = Iter.create dir trav s

let _ = Iter.iter (fun k -> print_string (string_of_int k ^ " ")) iter
-----------

which prints out
  1 2 3 4

What is the semantics of Traverse_While? I was expecting the iterator to
stop at 3. The iterator seems to go one element extra. Trying with m = 0
prints the value 1 even though the predicate given to Traverse_While is
never satisfied.

Also, leave m = 3, and remove 2 from the list. Then we get Exception:
Failure "get_value".
Alternatively, leave the list as shown above and set m = 7. I was expecting
same error again, but there is no Failure this time.

Re: [Ocaml-reins-devel] possible installation bug

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

Ashish Agarwal wrote:
> Hi. I kept getting "Unbound module Reins" error, until I manually copied 
> reins.cmi to the installation directory. It was not copied there by 
> "omake install". Is this a bug in the installation script?

Yeah, the install target is broken in a couple of ways that have all 
been fixed in the svn version.  I'm planning on making another release 
in about 2-3 weeks time with several improvements and a few more data 
structures (the author of Baire emailed me with some of his earlier 
work, so some of that will be included too).

Thanks for the message.

Cheers,
-m

[Ocaml-reins-devel] possible installation bug

[Ashish A. <aga...@gm...>]

Hi. I kept getting "Unbound module Reins" error, until I manually copied
reins.cmi to the installation directory. It was not copied there by "omake
install". Is this a bug in the installation script?

Re: [Ocaml-reins-devel] A debian package for reins release ?

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

On Wed, 3 Oct 2007, Fabrice Marchant wrote:

>  Hi !
Hello.

>  I've discovered reins library in OCaml list and looked a bit at the
> code ( double queue ). Very interesting and purely functional : great !
>
>  However I've not yet fully installed it on my debian Lenny ( Objective 
> Caml version 3.09.2 ).
>
> Please has someone soon debianized reins as a Lenny package ?

I have made a Debian package and uploaded to the Debian archive.  Since 
it's a new package, it has to be approved by the ftp-masters, but that 
should only take another day or two at which point it will enter unstable. 
You can then either wait (10 days more) for it to propogate to testing 
(Lenny), or build it yourself in the meantime by grabbing it from the 
debian OCaml packages svn:

   http://svn.debian.org/wsvn/pkg-ocaml-maint/trunk/packages/ocaml-reins/

which can be built using the svn-buildpackage tool.

If you run into any problems, let me know and I can probably create a .deb 
for you.

Cheers,
-Mike

[Ocaml-reins-devel] A debian package for reins release ?

[Fabrice M. <fab...@fr...>]

  Hi !

  I've discovered reins library in OCaml list and looked a bit at the
code ( double queue ). Very interesting and purely functional : great !

  However I've not yet fully installed it on my debian Lenny ( Objective Caml version 3.09.2 ).

Please has someone soon debianized reins as a Lenny package ?

Thanks for the help.

  Fabrice