4 ms·

Show HN: A LRU cache using go generics

57 points by _256 5y ago

_256 5y ago
This is a simple LRU cache I made to get my hands on generics which is available in the go 1.18 beta. Feedback is welcome :-)
- deleted 5y ago
  [deleted]
- bogomipz 5y ago
  Might you or anyone else have any good links or references that helped you come up to speed on generics in Go?
  - meling 5y ago
    The tutorial from the Go team is pretty good to learn the basics: https://go.dev/doc/tutorial/generics https://go.dev/doc/tutorial/generics
  - feffe 5y ago
    There's also the type parameters proposal document which covers a lot of ground. https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md https://go.googlesource.com/proposal/+/refs/heads/master/des...
morelisp 5y ago
> Feedback is welcome You'll probably be a lot better off a) preallocating the elements so your memory is nicely contiguous, b) tracking indices and not pointers. If I wanted to pay 24b overhead per item I'd use an `interface{}`. :)
- olliej 5y ago
  Which pointer are you wanting to replace, there are a few and I can’t work out which would be best replaced with an int :) (not the author, and not a go developer, just reading through the code and couldn’t work out which you were talking about :) ) Similar for what you want to preallocate.
  - deleted 5y ago
    [deleted]
  - morelisp 5y ago
    Preallocate the map and the entry ({V, next, prev}) objects. Replace next and prev and the map value with indices.
- omegalulw 5y ago
  If they track indices, how would they index new elements upon deletion of old ones? They need to maintain a hashset of free indices?
  - omegalulw 5y ago
    (answering myself) Nope, they don't. They just need to keep a list of free indices when the cache is not full. Upon eviction you reuse the deleted element's index. This way, you store about O(capacity)*32bits for index in the worst case and save 32bits on left, right and the map pointers so your worst case space complexity is down by O(capacity). I still expect that the saving from cache friendliness with preallocation will be the most significant. Very thoughtful optimization. I'm usually guilty of just caring about Big O, usually just the time complexity.
    - omegalulw 5y ago
      Sry, the space complexity isn't improved, you save capacity322 bits though.
      - morelisp 5y ago
        If you parameterize on the type of capacity you can save even more. (But yes, same complexity - only in rare cases will you manage to store n values without O(n) memory. :) ) In Go, types without pointers also make the GC's life easier. https://go.dev/src/runtime/mheap.go#L525 https://go.dev/src/runtime/mheap.go#L525

57 points by _256 5y ago

_256 5y ago

This is a simple LRU cache I made to get my hands on generics which is available in the go 1.18 beta. Feedback is welcome :-)

deleted 5y ago
[deleted]
bogomipz 5y ago
Might you or anyone else have any good links or references that helped you come up to speed on generics in Go?
- meling 5y ago
  The tutorial from the Go team is pretty good to learn the basics: https://go.dev/doc/tutorial/generics https://go.dev/doc/tutorial/generics
- feffe 5y ago
  There's also the type parameters proposal document which covers a lot of ground. https://go.googlesource.com/proposal/+/refs/heads/master/design/43651-type-parameters.md https://go.googlesource.com/proposal/+/refs/heads/master/des...

morelisp 5y ago

> Feedback is welcome You'll probably be a lot better off a) preallocating the elements so your memory is nicely contiguous, b) tracking indices and not pointers. If I wanted to pay 24b overhead per item I'd use an `interface{}`. :)

olliej 5y ago
Which pointer are you wanting to replace, there are a few and I can’t work out which would be best replaced with an int :) (not the author, and not a go developer, just reading through the code and couldn’t work out which you were talking about :) ) Similar for what you want to preallocate.
- deleted 5y ago
  [deleted]
- morelisp 5y ago
  Preallocate the map and the entry ({V, next, prev}) objects. Replace next and prev and the map value with indices.
omegalulw 5y ago
If they track indices, how would they index new elements upon deletion of old ones? They need to maintain a hashset of free indices?
- omegalulw 5y ago
  (answering myself) Nope, they don't. They just need to keep a list of free indices when the cache is not full. Upon eviction you reuse the deleted element's index. This way, you store about O(capacity)*32bits for index in the worst case and save 32bits on left, right and the map pointers so your worst case space complexity is down by O(capacity). I still expect that the saving from cache friendliness with preallocation will be the most significant. Very thoughtful optimization. I'm usually guilty of just caring about Big O, usually just the time complexity.
  - omegalulw 5y ago
    Sry, the space complexity isn't improved, you save capacity322 bits though.
    - morelisp 5y ago
      If you parameterize on the type of capacity you can save even more. (But yes, same complexity - only in rare cases will you manage to store n values without O(n) memory. :) ) In Go, types without pointers also make the GC's life easier. https://go.dev/src/runtime/mheap.go#L525 https://go.dev/src/runtime/mheap.go#L525