Re: [Ocaml-lib-devel] ExtList: using _setcdr instead of Obj.magic

[Brian H. <bri...@ql...>]

On Tue, 22 Apr 2003, Nicolas Cannasse wrote:

> > > It is called , it should actually be called when call - complexity is
> lower
> > > than O(n) since the overhead is not big.
> >
> > Which is never in list functions, that I know about.
> 
> I was talking about complexity in term of numbers of calls to _setcdr.
> BTW, you're right, I'm not sure there is functions with only one call to
> _setcdr

So was I.  I can't think of a function that calls _setcdr that doesn't 
call it O(n) times.  Which means we never called _setcdr- I remember 
grepping for it and not finding it.

> 
> > I've yet to hear this in a case where it turned out to be so.
> 
> This will need a very major changes in the entire Ocaml sources since it
> will involve modifying the current memory representation, and I'm pretty
> sure it won't happen before few years.

Yeah, this does strike me as being an unlikely change.  How many different 
formats are there for an immutable linked list are there?  2?  data then 
next, or next then data.  They chose the first one.  And I don't see any 
advantage to them switching.

> 
> > And I
> > notice the changes are sneaking out of ExtList- I note that Enum has an
> > Obj.magic call which is effectively _setcdr.  On my to-do list was to take
> > a long hard look at Enum.force to see if I could move that _setcdr back
> > into ExtList where it belongs.
> 
> From my point of view, the setcdr is a trick which should of course not be
> put in the interface extList.mli ( we agreed on that before ). And so if you
> want to use it in Enum, you have to rewrite it. This is a performance trick,
> since we could always build the list in the other way and then rev it, and a
> safe trick since we could instead use a non tail-rec call.
> As a performance trick , it should be inlined.
> As a safe trick, it shouldn't be shown to the user, and a _setcdr function
> shouldn't even exists :)
> 

OK.  You talked me into it.  _setcdr goes away, and I'll replace 
everything with Obj.magic calls.

Brian