ocaml-lib-devel

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

[Brian H. <bh...@sp...>]

Went through and changed all the inlined _setcdr calls to normal _setcdr 
calls.

a) If we never call the function, why define it?

b) function calls aren't that expensive.  And _setcdr is probably inlined 
in most cases anyways.

c) In the future, when we have to change the magic incantation to make it 
work, we only have to change it once, in _setcdr, and not all over.

Brian

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

[Nicolas C. <war...@fr...>]

> Went through and changed all the inlined _setcdr calls to normal _setcdr
> calls.

Uh ! it took me some time to inlined them :'(

> a) If we never call the function, why define it?

It is called , it should actually be called when call - complexity is lower
than O(n) since the overhead is not big.

> b) function calls aren't that expensive.  And _setcdr is probably inlined
> in most cases anyways.

In native code, there is no problem with it.
In bytecode, the speedups are around 20% and since we're working an on
Standard library, it would be good to provide efficient code to the
community, don't you think ? That's why after lots of benchs and differents
versions I ended up inlining the calls.

> c) In the future, when we have to change the magic incantation to make it
> work, we only have to change it once, in _setcdr, and not all over.

We will never have to do so.
And if we do, I volunteer to make the changes.

Nicolas Cannasse

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

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

On Mon, 21 Apr 2003, Nicolas Cannasse wrote:

> > Went through and changed all the inlined _setcdr calls to normal _setcdr
> > calls.
> 
> Uh ! it took me some time to inlined them :'(

Then I wish you had asked me before doing so.  As I'm opposed to it.

> 
> > a) If we never call the function, why define it?
> 
> 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.

> 
> > b) function calls aren't that expensive.  And _setcdr is probably inlined
> > in most cases anyways.
> 
> In native code, there is no problem with it.
> In bytecode, the speedups are around 20% and since we're working an on
> Standard library, it would be good to provide efficient code to the
> community, don't you think ? That's why after lots of benchs and differents
> versions I ended up inlining the calls.

Hmm.  I'm less concerned about performance with bytecode.  Bluntly, if you 
want speed, go native.  If you're going bytecode, you're giving up a lot 
of speed anyways.  But I'm still surprised it's not inlined in the 
bytecode case as well.  Just to check- you did use -inline, right?

> 
> > c) In the future, when we have to change the magic incantation to make it
> > work, we only have to change it once, in _setcdr, and not all over.
> 
> We will never have to do so.

I've yet to hear this in a case where it turned out to be so.  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.

Brian

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

[Nicolas C. <war...@fr...>]

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

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

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

Nicolas Cannasse

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