11–14 of 14 posts
> 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{}`. :)
> 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{}`. :)
If they track indices, how would they index new elements upon deletion of old ones? They need to maintain a hashset of free indices?
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.
Earlier quoted context omitted.
If they track indices, how would they index new elements upon deletion of old ones? They need to maintain a hashset of free indices?
(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 preallocati…
Earlier quoted context omitted.
(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 preallocati…
Sry, the space complexity isn't improved, you save capacity 32 2 bits though.
In Go, types without pointers also make the GC's life easier. https://go.dev/src/runtime/mheap.go#L525