Re: Ancient, concurrency, etc.

Re: Ancient, concurrency, etc.

[Berke Durak]

[-- Attachment #1: Type: text/plain, Size: 3460 bytes --]

On Sat, May 10, 2008 at 10:51 AM, Richard Jones <rich@annexia.org> wrote:

>
> > As you cannot mutate anything that is ancient (since it might be
> > concurrently
> > accessed),
>
> There are various restrictions on mutating the ancient data, which are
> explained in the README.  It is not true that ancient data is
> completely immutable, just that you really need to understand what
> you're doing in order to do it correctly.


I'm not talking of mutating atomic values here.

I'm saying that you certainly can't have the GC or someone else mutate the
data for
traversal purposes.


>  There are additional
> restrictions to mutating [any] data concurrently, but I didn't explain
> those because they are obvious, and can be solved with standard
> threading techniques (mutexes, etc.)..
>
> > you cannot mark or modify them in-place for ad-hoc marshalling or
> > deep copying.  Is that correct?
>
> I'm not sure what this means.  I haven't tried to Marshal ancient
> data, because ancient data can already be persisted, so marshaling it
> doesn't make much sense.

'Deep copying' of ancient data can be done just like deep copying any
> other OCaml value.


As in: it can't be done polymorphically, unless you resort to Marshal, which
doesn't work on ancient data.


> > Comparison does not mark (and thus does not work on cyclic structures).
> > Does it work on values in the ancient heap (I'm not talking of handles
> > here)?
>
> Your use of 'value', 'handle' etc. is confusing me.


By handle I meant values behind of type 'a ancient.


> I suggest you
> take a look at how OCaml values are stored (eg. <caml/mlvalues.h> is a
> good place to start).


I suggest you look at extern.c & intern.c to see how Ocaml values are
marshalled.
A joke of course, I assume you already know.

Anyhow, the polymorphic primitives (like %compare) don't work, just
> because they make the assumption that anything outside the normal
> OCaml heap is incomparable


And that can be quite annoying, so we'd like a way to take values of out
the ancient heap.


> , but you can certainly write your own
> comparison functions to replace those, eg. comparing
> character-by-character for strings.


Not. Polymorphic.


> This has nothing to do with 'marking'.


Well, walking over a value graph, either for complete
hashing/comparison/copying or
serialization requires marking unless your graph is a tree.

> So it seems that adding a generic copy-out-of-the-ancient heap function
> > (which marks in a private area) would be worthwhile.  Should not be too
> > difficult.
>
> As I said earlier, you can just copy values from the ancient heap as
> you would any other value, eg. using { ... with ... } syntax or
> Array.copy / String.copy etc.


That is not polymorphic.

Let's say this again.  Values on the ancient heap look just like
> values anywhere else in the program.  You can pass them to functions,
> print them out, add them up, do whatever else you would normally do,
> with very few restrictions.  The differences are:
>
>  - the polymorphic primitives don't work (so you can't compare or hash
> them)


That's very annoying for what I had in mind: communication for concurrency.


>   - they don't get garbage collected


Again, if you want to store an ancient value in a new one, you're toast.

- you should be very careful about mutating them


That I can understand.  Something like

  val Ancient.get : int -> 'a(immutable)

would have been nice.

-- 
Berke

[-- Attachment #2: Type: text/html, Size: 5922 bytes --]

Re: Ancient, concurrency, etc.

[Richard Jones]

On Sat, May 10, 2008 at 11:09:04AM +0200, Berke Durak wrote:
> On Sat, May 10, 2008 at 10:51 AM, Richard Jones <rich@annexia.org> wrote:
> 'Deep copying' of ancient data can be done just like deep copying any
> > other OCaml value.
> 
> As in: it can't be done polymorphically, unless you resort to Marshal, which
> doesn't work on ancient data.

I don't understand -- is there a case where you're using Ancient and
the lack of Marshal has stopped you from doing something?  Or is this
just a really abstract argument about limitations that real users will
never encounter.  I myself have used Ancient extensively and the lack
of Marshal has never been a problem.

> > Anyhow, the polymorphic primitives (like %compare) don't work, just
> > because they make the assumption that anything outside the normal
> > OCaml heap is incomparable
> 
> And that can be quite annoying, so we'd like a way to take values of out
> the ancient heap.

Lack of polymorphic compare is a limitation, but it's well understood
and very simple to work around, and the workarounds don't require
copying anything out of (or into) any heap.

> > , but you can certainly write your own
> > comparison functions to replace those, eg. comparing
> > character-by-character for strings.
> 
> Not. Polymorphic.

But why?  For what purpose?  Any OCaml structure I can think of lets
you define your own comparison or hashing function, so this is no
barrier to putting Ancient objects into Maps or Hashtbls or whatever.

> > This has nothing to do with 'marking'.
> 
> Well, walking over a value graph, either for complete
> hashing/comparison/copying or
> serialization requires marking unless your graph is a tree.

Yes, and marking works just fine with Ancient objects, since their
in-memory representation is *exactly the same* as ordinary heap
objects.  You can mark them just fine by playing with the GC-reserved
bits in the header or however else you normally do it.

> That's very annoying for what I had in mind: communication for concurrency.

Ancient is designed for sharing large mostly read-only data sets
between processes.

It happens that you can mutate simple data too -- eg. if lots of
worker threads are writing their results to a big shared matrix, that
will work fine too.

It also happens that you could use Ancient to pass messages between
processes too.  You'll have to use futexs to provide mutual exclusion
and you'll have to manually free messages after using them, but the
overhead of passing a message will be just one or two copies (from
Caml heap to ancient heap and if necessary from ancient heap to Caml
heap at the remote end).  [The real overhead is hidden in this
analysis since if the processes are running in different sockets then
there will be unavoidable hardware message passing, lots of nasty
cache effects and so on, that you must take account of].

> >   - they don't get garbage collected
> 
> Again, if you want to store an ancient value in a new one, you're toast.

Store an ancient value in a new what?

Anyway, I've had enough of this pointless back and forth.  If you are
using Ancient and have actual sensible questions about its use, please
contact me in the normal way for open source projects.

Rich.

-- 
Richard Jones
Red Hat

Re: Ancient, concurrency, etc.

[Berke Durak]

[-- Attachment #1: Type: text/plain, Size: 739 bytes --]

Richard,

There is no need to get angry.

Ancient is a nice and useful module.  Thank you for writing and sharing
it.

You brought it forward as a solution for inter-process message-passing after
I proposed a faster Marshal designed for shared memory IPC.  Ancient could
fulfill that role, provided someone writes a way to copy a value out of the
ancient heap, otherwise we'll (a) miss the usual polymorphic operators and
(b) risk storing dangling references or inappropriately mutating ancient
values.  That's just a small function and would increase the usefulness of
your module.

PS.Maybe a 64-bit address space would be enough to generate a unique address
for every ancient value so that they could be deleted using munmap.
-- 
Berke

[-- Attachment #2: Type: text/html, Size: 827 bytes --]

Re: [Caml-list] Re: Ancient, concurrency, etc.

[Jon Harrop]

On Saturday 10 May 2008 10:09:04 Berke Durak wrote:
> On Sat, May 10, 2008 at 10:51 AM, Richard Jones <rich@annexia.org> wrote:
> > There are various restrictions on mutating the ancient data, which are
> > explained in the README.  It is not true that ancient data is
> > completely immutable, just that you really need to understand what
> > you're doing in order to do it correctly.
>
> I'm not talking of mutating atomic values here.

I assume Richard was referring to injecting references from the ancient heap 
into the live heap using mutation. If the value were later moved on the live 
heap then the OCaml run-time would not know to update the pointer in the 
ancient heap and you would get a dangling pointer.

> I'm saying that you certainly can't have the GC or someone else mutate the
> data for traversal purposes.

I believe the GC will never try to traverse it so it will not mutate it.

> > I'm not sure what this means.  I haven't tried to Marshal ancient
> > data, because ancient data can already be persisted, so marshaling it
> > doesn't make much sense.
> > 'Deep copying' of ancient data can be done just like deep copying any
> > other OCaml value.
>
> As in: it can't be done polymorphically, unless you resort to Marshal,
> which doesn't work on ancient data.

Or memcpy.

> > because they make the assumption that anything outside the normal
> > OCaml heap is incomparable
>
> And that can be quite annoying, so we'd like a way to take values of out
> the ancient heap.

This is exactly the incidental complexity I was referring to.

> > , but you can certainly write your own
> > comparison functions to replace those, eg. comparing
> > character-by-character for strings.
>
> Not. Polymorphic.

Use memcmp. :-)

> > This has nothing to do with 'marking'.
>
> Well, walking over a value graph, either for complete
> hashing/comparison/copying or
> serialization requires marking unless your graph is a tree.

Not really. There are two problems here. Firstly, OCaml's built in hashing, 
comparison and equality blindly recurse without checking for cycles so they 
do not need any metadata. Secondly, you can store the traversal data outside 
the graph: there is no need to mark it.

> > So it seems that adding a generic copy-out-of-the-ancient heap function
> >
> > > (which marks in a private area) would be worthwhile.  Should not be too
> > > difficult.
> >
> > As I said earlier, you can just copy values from the ancient heap as
> > you would any other value, eg. using { ... with ... } syntax or
> > Array.copy / String.copy etc.
>
> That is not polymorphic.

If we have a type:

  type t = { x: float; n: int }

with a value of that type in the ancient heap and we do:

  let local = { ancient with n=3 }

then we have created a shallow copy that has now pulled a pointer to the boxed 
float value in the ancient heap into our GC which will later try to 
deallocate that float and crash. Is that correct?

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e

Re: [Caml-list] Re: Ancient, concurrency, etc.

[Richard Jones]

On Sun, May 11, 2008 at 05:15:52AM +0100, Jon Harrop wrote:
> If we have a type:
> 
>   type t = { x: float; n: int }
> 
> with a value of that type in the ancient heap and we do:
> 
>   let local = { ancient with n=3 }
>
> then we have created a shallow copy that has now pulled a pointer to
> the boxed float value in the ancient heap into our GC which will
> later try to deallocate that float and crash. Is that correct?

No.  This creates a local value on the OCaml heap, containing a
pointer to x on the ancient heap, but this won't cause a crash because
the GC will just ignore that pointer.

The problem, as you said earlier, is with pointers from ancient to the
Caml heap, where you can end up with a dangling pointer (from ancient)
which if followed would cause a crash or some other sort of nasty
failure.  (Not dissimilar to the case where you unmarshal something
with the wrong type).

Rich.

-- 
Richard Jones
Red Hat