why is Array said to be slow?

[Raoul Duke]

hi,

'On the server side, it's often better to use a "List" which is less
memory and CPU consuming, unless you really need indexed access.'

what are the salient details of performance differences? (i don't
understand why an array would be slower than a list, at least if the
array is small and fits in the cache, since that would be one less
level of indirection for the memory system to have to deal with vs. a
linked list.)

thanks.

[Cauê Waneck]

I think this information is outdated. AFAIK List is much slower than Array in all targets.

2012/8/14 Raoul Duke <rao...@gmail.com>

--
To post to this group haxe...@googlegroups.com
http://groups.google.com/group/haxelang?hl=en

[Raoul Duke]

AUGH!

of course, i probably shoulda known that the docs are EVIL, but still...

thanks for your reassurance :-)

[Cauê Waneck]

Where did you find this info?

2012/8/14 Raoul Duke <rao...@gmail.com>

[Raoul Duke]

uhm, like, one of the very first things on
http://haxe.org/api/array

[Lee Sylvester]

I think I mention that same thing, and describe why, in the old book, too.
This needs to be updated :-)

[dlots]

I use array basically everywhere. On swf and neko they are essentially equal in my rudimentary benchmarks.

[David Holaň]

My flash benchmarks show array being quite slow in comparison to optimized linked lists - FastList and my implementation of singly and doubly linked list. But it's still a lot faster than List.

0.786 Haxe_List
0.434 ARRAY_MANUAL
0.357 Haxe_FastList_Manual
0.212 Dd_LinkedList
0.209 Dd_SinglyLinkedList
0.101 ARRAY
0.046 Dd_SinglyLinkedList_Manual
0.040 Dd_LinkedList_Reverse
0.035 Dd_LinkedList_Manual
0.031 Dd_SinglyLinkedList_Fast
0.017 Haxe_FastList
0.015 For
0.014 While

Scores postfixed with "Manual", "Fast" and "Reverse" used this form of iteration:

var iterator = structure.iterator();
while( iterator.hasNext() ) {
    x += iterator.next();
}

This form of iteration benefits from inline iterator methods.

Dd_SinglyLinkedList_Fast iterator has some functionality stripped so it a bit faster.

Dd_LinkedList_Reverse iterator iterates from the end to the beginning.

Scores without postfix used this form of iteration:

for( i in structure ) {
    x += i;  
}

"While" stands for:

var i = 0;
while ( i < range )
{
    x += i;
    ++i;
}

"For" stands for:

for ( i in 0...range )
{
   x += i;
}

Let's check the results from fastest to slowest:

0.015 For
0.014 While

Very fast as expected.

0.017 Haxe_FastList

For iteration is very optimized on the compiler level so it ranked right behind for and while.

0.046 Dd_SinglyLinkedList_Manual
0.040 Dd_LinkedList_Reverse
0.035 Dd_LinkedList_Manual
0.031 Dd_SinglyLinkedList_Fast

My implementations using manual iteration follow. This shows the benefit of inlined iterator methods.

0.101 ARRAY

Array time is quite good. There are probably some compiler optimizations at work here.

0.212 Dd_LinkedList
0.209 Dd_SinglyLinkedList

My implementations using for iteration follow. The hit from calling iterator methods rather than inlining them is apparent.

0.357 Haxe_FastList_Manual

It seems manual iteration is missed by optimization of for iteration and ends up with a very bad time.

Array manual iteration follow. Probably same

0.786 Haxe_List

Epic fail :] Probably no inlining here. Also List uses arrays internally to store links. If it used class fields it would perform better on flash. I think manual iteration is quite the same, so it is omitted from benchmark.

[Cauê Waneck]

Nice benhmarks, david!

And yes, we need to optimize List, which is really unoptimized atm, I think on all platforms

2012/8/14 David Holaň <paladin....@gmail.com>

[David Holaň]

Forgot one important bit: Lists/arrays were initialized with range 0...1500 and iterations were repeated 1000 times. The results is time in seconds.

-David

2012/8/14 David Holaň <paladin....@gmail.com>

[Justin Donaldson]

I remember writing this up a long time ago:

http://haxe.org/com/libs/listtools/which_iterable_type_should_i_use_

It talks a bit about speed, and the differences between list implementations.

There's a reference to  SugarList in there.  It shares the same api as List, but internally it operates more like FastList:

https://github.com/jdonaldson/sugar-tools/blob/master/src/org/sugar/collections/SugarList.hx

It's much faster in swf, but swf is no longer a focus for me, so I don't use it at all.

Looking forward to Haxe 3.0, I believe Nicolas wanted to call FastList a "Stack" for Haxe 3.0.  This makes sense, since FastList operates a bit differently than List (FastList adds to its head.... like a stack). 

Since Haxe 2.0 was released, we've had the big "JS boom" with V8, sunspider, etc.  I'm not sure exactly how they do it, but arrays are list-like and extremely fast and efficient on these newer vms.  They probably should be the default List implementation when using --js-modern.

The Lambda class should also be mentioned, it's currently tied to that default List class.  With all the functional/typing features of Haxe, Lambda+List should be more Lamborghini, and less lagging. :)

Best,

-Justin

  

blog: http://www.scwn.net
twitter: sudojudo

[Raoul Duke]

i'll state what i take to be The Obvious, just for the record: some
day down the road, it would seem to me that it would be great if haxe:

(1) defined some core interfaces / structure shapes for core
collections, at least array/list. these interfaces should be good,
rather than strange and anemic like the ones in core haxe to date.
(presumably polygonal, or the jdk, or scala, would be things to study
for hints.)

(2) implemented a toolkit that can choose the fastest implementation
per final targeted language/platform.

(3) set it up to allow contributions so that over time it could become
more finessed for all the various possible targets.

(4) had structure so that testing was built-in to the suite, run on
every commit, and easy for anybody to run themselves locally.

even just for 1D types, let alone associative ones or anything else,
that would be a pretty cool step forward.

sincerely.

[Max]

> I don't understand why an array would be slower than a list?

Correct me if I'm wrong!!!

Array is using hash!

        var a = new Array<Int>();
        a[100] = 10; // no error since index 100 is a hash key
        trace(a[100]); // traces 10
        trace(a[99]); // traces null on dynamic platforms, or 0 on static

If I remember clearly, proposal (Haxe3?) is to use Vector class for raw index access.

[Raoul Duke]

On Tue, Aug 14, 2012 at 2:55 PM, Max <max.v...@googlemail.com> wrote:
> Correct me if I'm wrong!!!
> Array is using hash!

> If I remember clearly, proposal (Haxe3?) is to use Vector class for raw
> index access.

oh, okay.

...so i must add another thing to my The Obvious list :-)

(5) there must be accurate up-to-date docs that say what the various
underlying implementations actually are using. (the test suite and the
reports it generates and makes public on every build should make it
clear as well.)

[Nicolas Cannasse]

Le 14/08/2012 18:54, Raoul Duke a �crit :

> hi,
>
> 'On the server side, it's often better to use a "List" which is less
> memory and CPU consuming, unless you really need indexed access.'

Arrays and Lists are two different containers :

- array is not very good for insertion / deletion (in general you will
need to copy the whole array content when doing so), but great for
random access

- list is good for insertion / deletion, although for small sets they
should not make much difference compared to small arrays. List is also
stable wrt iteration (ie you can safely remove an element from a list
while iterating on it) which is not the case for array.

Best,
Nicolas

[杨博]

在 2012年8月15日星期三UTC+8下午7时19分47秒，Nicolas Cannasse写道：

Le 14/08/2012 18:54, Raoul Duke a �crit :

> hi,
>
> 'On the server side, it's often better to use a "List" which is less
> memory and CPU consuming, unless you really need indexed access.'

Arrays and Lists are two different containers :

- array is not very good for insertion / deletion (in general you will
need to copy the whole array content when doing so), but great for
random access

I used to think that an Array is a hash table, isn't it? Or it is a hash table for some platform, but not for all platform. Right?

[Justin Donaldson]

Here's a neat test you can run in your browser:

http://jsperf.com/object-vs-array-vs-native-linked-list/3

And an explanation:

http://blog.pic-o.com/2011/12/divlinkedlist/

It's pretty amazing to see hundreds of millions of operations per second in a browser.  Lists are still faster than arrays at inserting (to the middle).  However, do many people insert into the middle of a list much? 

Regardless of how the std container types develop, I think people will want to use lambda methods based on arrays for js in newer web browsers.  Franco's thx library (Arrays.hx) is already good for that I think:

https://github.com/fponticelli/thx

Best,

-Justin

--

To post to this group haxe...@googlegroups.com
http://groups.google.com/group/haxelang?hl=en