Re: [Ocaml-lib-devel] iterator semantics

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

On Thu, 6 May 2004, Nicolas Cannasse wrote:

> > I'd like to reconsider the iteration semantics of Enums.
> > So this is a thought experiment.
> [...]
> 
> Sorry I didn't have time recently to answer the private talks we had about
> Enums specifications.
> My thinking is the following :
> Enum need more specification, but I want to keep them simple and unified. As
> you told, the only "good" way to have several types of enum is to use
> objects. I'm against it, simply because in stacked lazy operations such as
> map or filter, method lookup and call overhead is simply to high for
> something such as an enum. 

The lookup call isn't that expensive.  I just compiled the function:
	let f o = o#foo ();;
And got (x86 assembly):
        movl    8(%ebx), %ecx
        movl    %ecx, %edx
        andl    $1020, %edx
        shrl    $16, %ecx
        movl    (%eax), %ebx
        movl    (%ebx, %ecx), %ebx
        movl    (%ebx, %edx), %ecx
        movl    $1, %ebx
        jmp     caml_apply2
By comparison, the function:
	type 'a foo_t = { foo: unit -> 'a };;
	let f s = s.foo ();;
compiles to:
        movl    (%eax), %ebx
        movl    $1, %eax
        movl    (%ebx), %ecx
        jmp     *%ecx

Yeah, you're looking at a factor of three speed difference- but this 
amounts to only six instructions.  And the memory references are the real 
bottlenecks- 4 memory loads for the object, 2 memory loads for the record.

And I've spent a fair bit of time picking through the assembler output of 
Ocaml.  You're using the wrong language if you're worrying about every 
single instruction.

There *is* a problem with mapping.  Here's the problem- Ocaml, as it sits 
today can not correctly type the following function:
	class ['a] example =
		object
		method virtual map: 'b. ('a -> 'b) -> 'b example
		end

If I could move the map function inside the object (where, IMHO, it
belongs) I could write a really slick implementation which would collapse
multiple levels of maps into a single level, and would leave the only
remaining objection that I'm using objects and virtual functions.  
Unfortunately, I can't.  This means maps are externally applied.  Which 
means that multiple maps are always stacked.

This is especially bad, as I'd like to go with a functional enumerator 
class, for correctness reasons.

Now, if it was just me, I'd go "well, that's unfortunate", as I've yet to
come up with a situation where a) multiple maps are applied, and b) the
work done in each map is about the same amount of work as the
infrastructure of the map itself.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian