Re: [Ocaml-lib-devel] benchmarking enum approaches

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

> I wrote a little program to benchmark the three approaches I've seen
> discussed on the list for implementing streams/enums:
>
>   1.  (e.next ()) returns an option
>   2.  for-loop style, relying on the count (not suitable for
>       streams, including filtered enums)
>   3.  exception-catching style (the current implementation)
>
> It tests folds over maps of enums of constant ints.
[...]

Thanks, I get the same results on the windows MSVC version of OCaml. The
None/Some approach is really slow.
(BTW, I resolved Brian problem with having Enum exported next different from
imported one by renaming exported "next" to "peek")

Please notice that you're here testing for the best case, where count is
O(1) , but sometimes it can be O(N) or even worse since sometimes we need to
create an intermediate list and do a lot of I/O (reading a file for
example).
That leads to your next question...

> Another possibility would be to be clever about having fold and iter
> use (e.count ()) when it is fast, and use exception catching when
> (e.count ()) is slow, without actually having separate types.

Interesting. In the first time, I would say this is a good idea, since with
your benchs we can see that there is little improvement when iterating using
a O(1) counter against using an exception . But how can we tell that
e.count() is fast ? We can surely tells when it is slow : Enum.from could
put a boolean to true saying that the "worst count" will be called. But what
about Enum.make ? For example , ExtList.enum has an O(N) count, since we
don't want to count the elements we creating an enum ( this is the lazy
approach : do it only when we need it ).
When is the O(N) count faster than the exception catching ? I would say
"depends on the size of the list"... but we don't know the size :-) So if we
can classify "bad" counts we can't do it for "good" counts, and this
optimization will not work...

> So I think the question is:  is it worth a 10-20% performance hit in
> the library to unify the stream and enum types?

Which unification ? You mean, using None/Some next function ?
As excepted, the smaller the list is and the lesser there is map operations
applied on, then the better is None/Some performances compared to exceptions
one (note that you need 0 maps and list size less than 50 elements to have
None/Some being faster that exceptions).
My question is : when do we need speed ? For small lists when few operations
or for big lists with lots of operations ? With 5 maps on a 1000 elements
list, I got 200% speed using exceptions instead of None/Some.

Nicolas Cannasse