0.2 s to add a new element to a large array NOW WITH GRAPH!

Discussion about LiveCode Global Jam events and activities

Moderators: heatherlaine, Klaus, FourthWorld, robinmiller, kevinmiller

DarScott
Posts: 225
Joined: Fri Jul 28, 2006 12:23 am
Location: Albuquerque
Contact:

0.2 s to add a new element to a large array NOW WITH GRAPH!

Post by DarScott » Sat May 24, 2014 12:26 am

It takes a fifth of a second to add the millionth entry into an array.

Slow byte strings and slow arrays make for very boring days.
Last edited by DarScott on Sat May 24, 2014 1:37 am, edited 1 time in total.

DarScott
Posts: 225
Joined: Fri Jul 28, 2006 12:23 am
Location: Albuquerque
Contact:

Re: 0.2 s to add a new element to a large array

Post by DarScott » Sat May 24, 2014 12:53 am

My mistake. That is not the time to add the millionth element. That is the time to add the 561110th element of my test array.

Adding elements gets very slow between 553000 and 563000. And it somewhat slow over a wider range of 533000 through 563000.

DarScott
Posts: 225
Joined: Fri Jul 28, 2006 12:23 am
Location: Albuquerque
Contact:

Re: 0.2 s to add a new element to a large array

Post by DarScott » Sat May 24, 2014 1:35 am

Here is a plot of the time to build a array with integers as keys and integers as values:
Attachments
time to save array.png
seconds vs # elements

capellan
Posts: 415
Joined: Wed Aug 15, 2007 11:09 pm
Contact:

Re: 0.2 s to add a new element to a large array NOW WITH GRA

Post by capellan » Sat May 24, 2014 1:44 am

Could Operating System background operations be the real culprit?

If you repeat this test immediately after rebooting your computer,
Will you get the same results?

Al

DarScott
Posts: 225
Joined: Fri Jul 28, 2006 12:23 am
Location: Albuquerque
Contact:

Re: 0.2 s to add a new element to a large array NOW WITH GRA

Post by DarScott » Sat May 24, 2014 2:01 am

Here is the same data displayed with lines instead of dots:
Attachments
Time to build array graph.png

DarScott
Posts: 225
Joined: Fri Jul 28, 2006 12:23 am
Location: Albuquerque
Contact:

Re: 0.2 s to add a new element to a large array NOW WITH GRA

Post by DarScott » Sat May 24, 2014 2:29 am

Hi, Al! Here is what I got with less stat gathering overhead and after a reboot:
Attachments
time to build 2.png

capellan
Posts: 415
Joined: Wed Aug 15, 2007 11:09 pm
Contact:

Re: 0.2 s to add a new element to a large array NOW WITH GRA

Post by capellan » Sat May 24, 2014 2:50 am

Almost 15 seconds of delay!!! :?

What would be doing the engine in those 15 seconds?
Grabbing a big chunk of memory?
Creating indexes for accessing array elements?

The answer is in the source...
The engine source code! :shock:

Al

DarScott
Posts: 225
Joined: Fri Jul 28, 2006 12:23 am
Location: Albuquerque
Contact:

Re: 0.2 s to add a new element to a large array NOW WITH GRA

Post by DarScott » Sat May 24, 2014 6:23 am

I'm guessing that as each hash bucket gets filled, a bigger size and maybe bigger kind of bucket is created. They are good hashes, so they fill about the same time.
Last edited by DarScott on Sat May 24, 2014 9:30 pm, edited 1 time in total.

DarScott
Posts: 225
Joined: Fri Jul 28, 2006 12:23 am
Location: Albuquerque
Contact:

Re: 0.2 s to add a new element to a large array NOW WITH GRA

Post by DarScott » Sat May 24, 2014 9:09 pm

The time to access the array is constant, about 3 microseconds for me, but a little higher in the 500,000 to 600,000 zone.

DarScott
Posts: 225
Joined: Fri Jul 28, 2006 12:23 am
Location: Albuquerque
Contact:

Re: 0.2 s to add a new element to a large array NOW WITH GRA

Post by DarScott » Sat May 24, 2014 9:42 pm

It took 16 minutes to union two non-overlapping 500,000 element arrays. So, that is not a solution.

Another possibility would be to make an array of a thousand entries each with a thousand entries. I'd rather avoid that.

Maybe build with split?

DarScott
Posts: 225
Joined: Fri Jul 28, 2006 12:23 am
Location: Albuquerque
Contact:

Re: 0.2 s to add a new element to a large array NOW WITH GRA

Post by DarScott » Sat May 24, 2014 11:24 pm

The new arrayEncode(x,"7.0") packs arrays into half the size as before, but takes over twice as long. I'm good with that.

However, the arrayDecode(xe) is still slow. I would prefer it to be the faster one.

capellan
Posts: 415
Joined: Wed Aug 15, 2007 11:09 pm
Contact:

Re: 0.2 s to add a new element to a large array NOW WITH GRA

Post by capellan » Sat May 24, 2014 11:34 pm

Did you have a Test stack for this bug?

Al

DarScott
Posts: 225
Joined: Fri Jul 28, 2006 12:23 am
Location: Albuquerque
Contact:

Re: 0.2 s to add a new element to a large array NOW WITH GRA

Post by DarScott » Sat May 24, 2014 11:49 pm

Hi, Al!

I was about to say that I'm not sure it is a bug. It certainly is a nasty quirk. However, it has been slowing down today, and that is weird. It now takes 33 seconds. I'm up to 192 MB but I don't know what is normal for 7.0.

I have a stack. Not very clean. I have added some other buttons to see about a workaround and get other timing data. I'm currently looking at keeping a compressed empty array (integer-indexed) of size 650,000 or more in a custom property and popping it out every time I need an integer-indexed array larger than, say, 300,000.

It doesn't do the graph, it just puts csv data into a field. I did that as something quick to get a graph.

Would that be helpful? Is it possible to put stacks on the forum?

Simon
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 3900
Joined: Sat Mar 24, 2007 2:54 am
Location: Palo Alto

Re: 0.2 s to add a new element to a large array NOW WITH GRA

Post by Simon » Sun May 25, 2014 12:30 am

Would that be helpful? Is it possible to put stacks on the forum?
Yep, just zip them up first and they have to be under 256k(?)

Use the same method as posting pics.

Simon
I used to be a newbie but then I learned how to spell teh correctly and now I'm a noob!

DarScott
Posts: 225
Joined: Fri Jul 28, 2006 12:23 am
Location: Albuquerque
Contact:

Re: 0.2 s to add a new element to a large array NOW WITH GRA

Post by DarScott » Sun May 25, 2014 12:32 am

I tried building an million-element array with empty elements, indexed by consecutive integers. I compress( arrayEncode( it, "7.0")) and it got down to 1012 bytes! I saved that in a property. Now, for arrays with similar keys, I can pull this out for arrays bigger than 345,000 entries. (I'm thinking of making the saved one smaller so arrayDecode() is faster. It is slow for large arrays.)

Anyway, I was able to build my array in 6.4 seconds instead of the 24 seconds up.

I'll get the stack up soon.

Post Reply

Return to “LiveCode Global Jam”