npm package discovery and stats viewer.

Discover Tips

  • General search

    [free text search, go nuts!]

  • Package details

    pkg:[package-name]

  • User packages

    @[username]

Sponsor

Optimize Toolset

I’ve always been into building performant and accessible sites, but lately I’ve been taking it extremely seriously. So much so that I’ve been building a tool to help me optimize and monitor the sites that I build to make sure that I’m making an attempt to offer the best experience to those who visit them. If you’re into performant, accessible and SEO friendly sites, you might like it too! You can check it out at Optimize Toolset.

About

Hi, 👋, I’m Ryan Hefner  and I built this site for me, and you! The goal of this site was to provide an easy way for me to check the stats on my npm packages, both for prioritizing issues and updates, and to give me a little kick in the pants to keep up on stuff.

As I was building it, I realized that I was actually using the tool to build the tool, and figured I might as well put this out there and hopefully others will find it to be a fast and useful way to search and browse npm packages as I have.

If you’re interested in other things I’m working on, follow me on Twitter or check out the open source projects I’ve been publishing on GitHub.

I am also working on a Twitter bot for this site to tweet the most popular, newest, random packages from npm. Please follow that account now and it will start sending out packages soon–ish.

Open Software & Tools

This site wouldn’t be possible without the immense generosity and tireless efforts from the people who make contributions to the world and share their work via open source initiatives. Thank you 🙏

© 2024 – Pkg Stats / Ryan Hefner

bench-lru

v1.1.0

Published

benchmark the least-recently-used caches which are available on npm.

Downloads

6

Readme

bench-lru

benchmark the least-recently-used caches which are available on npm.

Introduction

An LRU cache is a cache with bounded memory use. The point of a cache is to improve performance, so how performant are the available implementations?

LRUs achive bounded memory use by removing the oldest items when a threashold number of items is reached. We measure 3 cases, adding an item, updating an item, and adding items which push other items out of the LRU.

There is a previous benchmark but it did not describe it's methodology. (and since it measures the memory used, but tests everything in the same process, it does not get clear results)

Benchmark

I run a very simple benchmark. In four phases:

  1. set the LRU to fit max N=100,000 items.
  2. add N random numbers to the cache, with keys 0-N.
  3. then update those keys with new random numbers.
  4. then evict those keys, by adding keys N-2N.

Results

Operations per millisecond (higher is better):

| name | size | gzip | set | get1 | update | get2 | evict | |-----------------------------------------------------|---------|---------|------|-------|--------|-------|-------| | tiny-lru | 4 kB | 1.64 kB | 4255 | 15385 | 20000 | 20000 | 4255 | | lru_cache | 2.19 kB | 756 B | 6452 | 18182 | 13333 | 14286 | 4878 | | simple-lru-cache | 1.43 kB | 565 B | 2273 | 13333 | 5714 | 25000 | 4255 | | hyperlru | 541 B | 339 B | 2247 | 15385 | 2667 | 20000 | 2632 | | hashlru | 628 B | 332 B | 6667 | 7407 | 7143 | 7692 | 4082 | | lru-fast | 2.34 kB | 793 B | 1887 | 8000 | 3030 | 9524 | 2151 | | lru | 6.07 kB | 1.86 kB | 2740 | 4255 | 4000 | 4444 | 1481 | | secondary-cache | 22.6 kB | 6.54 kB | 1802 | 2857 | 2857 | 6250 | 1587 | | quick-lru | 1.23 kB | 489 B | 3226 | 2273 | 3390 | 2222 | 1695 | | lru-cache | 19.1 kB | 6.23 kB | 704 | 2410 | 1299 | 2703 | 625 | | mkc | 10.5 kB | 3.61 kB | 862 | 1575 | 866 | 1575 | 775 | | modern-lru | 2.27 kB | 907 B | 671 | 1307 | 1205 | 1379 | 487 |

We can group the results in a few categories:

  • all rounders (tiny-lru, hashlru, lru-native, modern-lru, lru-cache) where the performance to add update and evict are comparable.
  • fast-write, slow-evict (lru_cache, lru, simple-lru-cache, lru-fast) these have better set/update times, but for some reason are quite slow to evict items!
  • slow in at least 2 categories (mkc, faster-lru-cache, secondary-cache)

Discussion

It appears that all-round performance is the most difficult to achive, in particular, performance on eviction is difficult to achive. I think eviction performance is the most important consideration, because once the cache is warm each subsequent addition causes an eviction, and actively used, hot, cache will run close to it's eviction performance. Also, some have faster add than update, and some faster update than add.

modern-lru gets pretty close to lru-native perf. I wrote hashlru after my seeing the other results from this benchmark, it's important to point out that it does not use the classic LRU algorithm, but has the important properties of the LRU (bounded memory use and O(1) time complexity)

Future work

This is still pretty early results, take any difference smaller than an order of magnitude with a grain of salt.

It is necessary to measure the statistical significance of the results to know accurately the relative performance of two closely matched implementations.

I also didn't test the memory usage. This should be done running the benchmarks each in a separate process, so that the memory used by each run is not left over while the next is running.

Conclusion

Javascript is generally slow, so one of the best ways to make it fast is to write less of it. LRUs are also quite difficult to implement (linked lists!). In trying to come up with a faster LRU implementation I realized that something far simpler could do the same job. Especially given the strengths and weaknesses of javascript, this is significantly faster than any of the other implementations, including the C implementation. Likely, the overhead of the C<->js boundry is partly to blame here.

License

MIT