7

I have checked each and every question and article about this, that I could find, but nothing really answers it. I make it sound as if I have just one question, there's more of them.

Maybe I should first explain what I am trying to do, I am building a File Manager entirely in JavaScript, the File Manager receives files from Backend (PHP, Twig), it then stores them in an array of Folder, each Folder has its own Files, Folders is an Array, and Files in each Folder is an Array as well, these Files are also shown on the page, and the user can select, copy, cut, paste ( other operations ) them ( I am still writing these operations, because here lies the problem ).
Files on page have data-id assigned to them, so that I can easily operate on them between File Manager and the Backend, and because I know the ID of every and each file, I think I could completely eliminate traversing through Arrays of Files in search of a particular File, if I could only create an Array that would take the ID of a File as an Index, and because this is JavaScript, I can do that! but there are some problems with it.

Trying to use an Object for this task just does not work, because it is just way slower than Array ( now, I understand, that the differences in speed, even if in millions, are not that big, but why not try to dig for ultimate performance, right ? )

So here is a list of questions, that I cannot seem to find a reliable answer to:

  1. Why is Object on Chrome so much faster, than Object on Firefox ?
  2. Why is accessing an undefined index on Chrome so much slower ?
  3. Why is Array so much faster on Firefox, than on Chrome ?
  4. I know why Chrome loses performance with higher indexes ( at 100k it transforms the array into a list, I think, it was answered with a link to source in another question on SO ), but Firefox loses performance gradually as if it traveresed to higher indexes sequentially, even if accessed directly, why is that ?
  5. Why is an Array extermely slow when there is only one element in it, but that element is at a very high index ?

There are probably some more questions I have, but I cannot think of them right now.

The fastest configuration I found, that supports IDs as indexes and holes between them, as well as starting at a high index, is using an Array that holds the data you want to store, and another array, that just holds the indexes, so that when you are searching for an object with ID 10, you touch the index Array, instead of the Array with data.
You can see an example of this in http://jsperf.com/array-management-performance/2.

EDIT: If you want to see the performance degradation, please "review" this jsperf and change minId and maxId to some big numebers.

Here are some stats:

Object

Read Defined: Firefox 165.173 mln ops/sec | Chrome 351.699 mln ops/sec
Read Undefined: Firefox 98.582 mln ops/sec | Chrome 54.666 mln ops/sec
Write Close: Firefox 7.599 mln ops/sec | Chrome 291.244 mln ops/sec
Write Far: Firefox 5.599 mln ops/sec | Chrome 93.733 mln ops/sec
Write Overwrite: Firefox 7.599 mln ops/sec | Chrome 291.244 mln ops/sec

Array

Read Defined: Firefox 681.206 mln ops/sec | Chrome 401.522 mln ops/sec
Read Undefined: Firefox 681.206 mln ops/sec | Chrome 62.827 mln ops/sec
Write Close: Firefox 400.234 mln ops/sec | Chrome 121.519 mln ops/sec
Write Far: Firefox 348.560 mln ops/sec | Chrome 121.519 mln ops/sec
Write Overwrite: Firefox 400.234 mln ops/sec | Chrome 234.337 mln ops/sec

P.S. Did you know, that Read Defined is faster on Chrome on Mobile, than on Chrome on Desktop ?

I jsperf-ed every single question I have here, so either my/others' tests were incorrectly written, or this is some really funky stuff.

http://jsperf.com/array-management-performance/2
http://jsperf.com/array-in-the-middle-of-nowhere
http://jsperf.com/object-holey-performance-better
http://jsperf.com/object-performance-better
http://jsperf.com/array-vs-object-mine-v2/5

P.S.2 I know, that one of the Array tests is actually testing Object, and another Object test is actually testing Array, please do not point that out, I am aware, I wrote this, the error is because jsperf is very poorly made, and I was trying to relatively quickly check a lot of different settings.

P.S.3 I am sorry, that some of these tests are really messy, I did not think, I would actually need to show them to anyone, but I still think there are sufficient.

---------------------------------------------------------------------------

EDIT: ( Answer, hopefully to re-open the question, so that I can answer it )

Here I go with an answer to all of our (my) problems. Now that I read my questions again, while having the answer, I can see how my questions could not be answered easily, or at all really, without digging into the sources of each browser.

I myself still do not know the exact answers to 1, 2, 3, 4 or even 5, but the answer that is correct, is "Because of implementation differences", it is as simple as that, obviously, I have not returned here to write just that, I have a solution to the problem I am showing in this question.

Simplified Problem: You have a set of IDs, that are assigned to data, most likely from the DB. You want that data in an array in JS, so that You can work with it very easily, but You DO NOT WANT to lose performance, while putting 100k elements into a JS array. How does one put N elements into an array in JS without losing read/write performance ? (I did not test write, because it is not that important to me).

Solution and Explanation: While studying this problem, I have checked a mutlitude of potential solutions, like splines, fourier transformations, hash tables, binary search, and a twist on map/hash tables, that actually performed VERY well, but not well enough for my taste ( it would also perform worse with the increase in size ).

The final solution seems dead simple and obvious, but somehow ( I guess I'm dumb ) it took me 10 days to figure out, it scales perfectly, and access to any element is extremely fast O(1).

To be able to write this solution, I use this property of JS engines http://jsperf.com/array-of-arrays-with-high-indexes/2 , it would seem, that access to first 1000 elements IS SUPER FAST ( even in arrays of arrays ), and because I know my data is unsigned integers, I can easily map the integers from 1D to 3D, so that FastArray can hold up to a Billion elements.

You can see this solution in action right here: http://jsperf.com/map-check-v2/5 -- The first test is slow, because I read the sample data from a simple array, and that is very slow ... EDIT: This does not seem to be the case, I really do not know what is causing it, I think jsperf is kind of freaking out, because running just that test yields pretty good results, very weird.

A cleaner implementation is here https://github.com/ImJustAskingDude/JavascriptFastArray with a lot of references to the every page I read, to try to figure this out.

P.S.4 Moderators. please re-open this question, so that people searching for Ultimate Array Performance can see this answer in a nice actual Answer. Thanks.

P.S.5 I do not know why, I guess there is a bug in my final code, that makes Chrome perform relatively poorly, which is probably easily fixable.

Improve this question
14
  • 2
    answers to 1,2,3 and 4. They perform differently because the underlying (JVM?) code is different. You wont get a more complete answer to questions 1-4 than that. Q5 - answer: because it is unusual to have a single element in an array at a high index, so that edge case is not optimized at the expense of more normal array usage Commented Oct 2, 2015 at 1:35
  • Re #5: that depends very much on what you're doing with the array. Looping over it from 0 to length, yes, slow, obviously, the compiler can't skip members just because they don't exist, you might be about to assign to it. However, native iterators like forEach and reduce skip missing members so not so slow on sparse arrays as loops. Commented Oct 2, 2015 at 2:48
  • 2
    why not try to dig for ultimate performance, right ? Because it's a diversion, and takes your attention away from writing clean, readable, writeable, maintainable, provably correct code. Commented Oct 2, 2015 at 4:40
  • @JaromandaX of course, I understand that the underlying code is different, but then again, arrays and objects are pretty much the same thing, as MDN points out, they are based on arrays, and if they are both based on arrays, then the underlying code should be pretty much the same right ? About accessing a high index, I cannot imagine, why would that be slower than accessing a low index, I know it is, but why ? Unless the array transforms into a list for a singular high index element, there is absolutely no reason for it to be slow, don't you think ? Commented Oct 2, 2015 at 10:49
  • @RobG You would be right, if it wasn't for the fact, that looping is mainly done by the programmer, at least I think it is, I write the loop, and I tell JavaScript which elements to access, so if I loop from 0, yea, it is going to loop from 0, but if I start the loop from that index, and go to that index + 10, I am pretty sure, it is going to access just those, but who knows, maybe you are right, could You conjure an example, where JavaScript would just outright ignore the programmer, and access those elements (not in a list) ( I am not being sarcastic, actually want to know ) Commented Oct 2, 2015 at 11:07

1 Answer 1

Reset to default
0

First of all, JS engines are different on every browser, so they don't perform equally on every case.

Also, you have to take in mind that arrays in JavaScript are Objects too, the only difference is that they have integers as their key values to simulate the indexes.

When you create an array with just one element at a high index the Object will be created with all the other "spaces" filled with undefined values so the JS engine have to traverse the whole structure to find your value.

As @RobG says, the native array methods like reduce, map, and forEach will perform a lot better in this case.

Also you can use functional libraries like Ramda or Lodash to help you traverse and flatten your queries results.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

the Object will be created with all the other "spaces" filled with undefined values I do not believe this is correct.
@torazaburo is absolutely right, there even is another question on SO, that debunks this belief, You can even check it yourself, by creating an array and console.log -ing it out, for one element, there is just going to be one element and no more than that, but if you create two elements, that are far apart, the "elements" in between are going to be marked <empty space> by console.log. I don't think they will actually be filled with anything, of course accessing them yields "undefined", but that's just accessing any variable with no assigned value.
I looked at Ramda and Lodash, but can't seem to understand how would they help me for a thing as relatively simple as this, I just want to have an array that performs reads and writes amazingly fast, I almost never have to traverse this array because of that (having the index, means I can just access elements directly). Maybe I should put this in my question ?
You don't mean JVM. JVM stands for Java Virtual Machine. This post is about javascript not Java. You mean JavaScript engine not JVM. Browsers do not use a JVM to execute JavaScript.
@user1494173 they will make your life easier on terms of data manipulation. BTW, why don't you provide a code example of your data so maybe we can play with it and see how we can help you improve the performance?

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.