search

vavr-io / vavr

vʌvr (formerly called Javaslang) is a non-commercial, non-profit object-functional library that runs with Java 8+. It aims to reduce the lines of code and increase code quality.
https://vavr.io
Other
5.68k stars 631 forks source link

Faster LinkedHashMap tail() #2725

Closed j-baker closed 1 year ago

j-baker commented 1 year ago

Change: LinkedHashMap tail() no longer copies the entire datastructure.

Motivation: We have a use case which looks somewhat like the following.

  1. It's effectively a Queue use case (fifo).
  2. Iteration order needs to be stable.
  3. Elements in the queue frequently need to be verified as present in the queue.
  4. Occasionally, removals must occur, which are usually from the head of the queue although occasionally randomly.

We started with a Queue and eventually found performance issues from too much linear scanning. This was not obviously going to be a bottleneck since our queues are usually of very small size, but ended up so. The next type we considered was a LinkedHashSet, using the head and tail methods to implement a dequeue-like operation and the set operations being sufficient for the other operations. Unfortunately, it seems that tail at present copies the entire queue despite not seemingly needing to.

We moved to our own hand-crafted HashSet+Queue structure, but this PR seems like it'd generally be beneficial for users of Vavr! It affects LinkedHashMap, and because LinkedHashSet contains a LinkedHashMap, LinkedHashSet, too.

j-baker commented 1 year ago

Thanks, Daniel! I appreciate the fast review + merge! When should I expect this code to be in a release?

danieldietrich commented 1 year ago

You're welcome. I can prepare a patch release this week!