New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Linked list is not faster than array! It was benchmarked incorrectly. #4

Closed
eldargab opened this Issue Mar 6, 2012 · 0 comments

Comments

Projects
None yet
2 participants
@eldargab

eldargab commented Mar 6, 2012

I tested linked list's performance more carefully and published results. It turned out that it's not faster.

So why there is 2 times gain in the fast-lists's benchmark:

for (var j = 0; j < l; j ++) {
  if (j % 2) list.push(j)
  else list.unshift(j)
}
for (var j = 0; j < l; j ++) {
   if (j % 2) list.shift(j)
   else list.pop(j)
}

That's because it fills list with both unshift() and push() as well as removes with both pop() and shift(). While pushes - pops of native Array are very fast, shifts - unshifts are slow. But for stacking we are doing only pushes and pops, for queueing - pushes and shifts. Linked list perfoms equally for add - remove operations on both sides. So, while benchmark above is correct for testing linked list's performance it depreciates array results.

@isaacs isaacs closed this in a240b4b Mar 6, 2012

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment