search

ThePrimeagen / BunSpreader

We spread the buns
74 stars 12 forks source link

JS / TS version uses a LinkedList vs Ringbuffer in Rust #4

Open dnlmlr opened 2 years ago

dnlmlr commented 2 years ago

The JS / TS List versions use a very classic linked list implementation. Linked list performance is generally pretty bad except for a few edge cases and a pure JS/TS implementation is likely the worst performance you can get for this.

The Rust VecDequeon the other hand uses a growable ring buffer. This is basically a Vec / ArrayList that keeps tracks of the head / tail indices and grows the buffer if the head touches the tail. This is in general significantly faster than you will ever get with a linked list.

Not sure where I'm going with this, but I guess the point is that the implementation details of the List give a major disadvantage to JS / TS from the start

dnlmlr commented 2 years ago

So I did a bit of testing and performance actually is getting worse when using a growing ringbuffer in node. This might be caused by my implementation or my lack of knowledge on nodejs internals and optimizations. Another possible cause could of course be my pretty bad testing methodology.

My implementation is here. It uses an Array for the actual storage and 2 indices for keeping track of the contents.

To test the performance I had it run on a cloudserver and blasted it from my desktop with 400 concurrent requests (causing 97% load on the single core server). I then looked at the response times, requests / second and the queue size.

dnlmlr commented 2 years ago

Ok I am definitely overthinking this whole thing, but I was curious and I looked a bit more into this. It seems that, at least in my testing, the queue was not a limiting factor. More tests had my VecDeque and the original List trading blows and both won sometimes.

So I made a small benchmark timimg how long it takes to queue a number of elements, dequeue half of them, queue the same number again and then dequeue all. I also added the "extremely fast and lightweight" Denque npm library to the comparison.

grafik

Turns out that the linked list (original List) scales very badly as expected. The VecDeque (ringbuffer) scales also as expected extremely well. I guess other parts of node or the webframework bottlenecked even harder than the queue in my testing.

Also that is exactly what I hate about a lot of JS libraries. So many of them claim to be "bLaZiNgLy fAsT" but get absolutely destroyed by some random puked out implementation.

Anyways here is the code for reference