LRU generics

[aviadl]

Added generics for all levels of LRU implementation For internal list, moved from GO built in containers/list to a generic implementation: github.com/bahlo/generic-list-go Updated all tests to accommodate generics In go.mod changed go version to 1.18

[hashicorp-cla]

All committers have signed the CLA.

[jefferai]

I don't know who would make this decision, but just a comment: likely to avoid breaking compatibility with earlier users we'd likely want to wait until either Go 1.18 is unsupported or make a v2 of the package.

[AskAlexSharov]

To avoid v2 introduction - can follow google/btree approach to introducing generics: https://github.com/google/btree/pull/45 leave existing types as is, and add new generic type:

 func (t *Btree)     Get(item Item) Item      { ... }
 func (t *BtreeG[T]) Get(item T)    (T, bool) { ... }

[jefferai]

@aviadl What are your thoughts on @AskAlexSharov 's suggestion? It makes sense to me as a good way to allow generics improvements but keep compatibility.

[aviadl]

@jefferai I think that working with go.mod would actually be better here Code would look nicer for the long run, instead of inventing a new object type

[SoMuchForSubtlety]

For internal list, moved from GO built in containers/list to a generic implementation: github.com/bahlo/generic-list-go

For my port of this library to use generics, I simply "vendored" containers/list, added generics and deleted unused code. That also has the useful side effect of being abele to get rid of the nested entries (LRU entry in a list entry).

This is the relevant code

benchmark results:

name         old time/op    new time/op    delta
2Q_Rand-16     1.22µs ±10%    0.52µs ± 8%   -57.69%  (p=0.000 n=20+19)
2Q_Freq-16     1.03µs ±10%    0.44µs ±12%   -57.42%  (p=0.000 n=18+20)
ARC_Rand-16    1.51µs ± 9%    0.70µs ±15%   -53.63%  (p=0.000 n=20+20)
ARC_Freq-16    1.22µs ±12%    0.54µs ± 7%   -56.20%  (p=0.000 n=20+20)
LRU_Rand-16     401ns ± 9%     215ns ± 6%   -46.46%  (p=0.000 n=20+20)
LRU_Freq-16     376ns ±13%     194ns ± 7%   -48.51%  (p=0.000 n=19+20)

name         old alloc/op   new alloc/op   delta
2Q_Rand-16       136B ± 0%       67B ± 0%   -50.74%  (p=0.000 n=20+18)
2Q_Freq-16       124B ± 0%       59B ± 0%   -52.42%  (p=0.000 n=16+20)
ARC_Rand-16      165B ± 0%       84B ± 1%   -49.03%  (p=0.000 n=20+20)
ARC_Freq-16      139B ± 3%       68B ± 5%   -51.01%  (p=0.000 n=20+20)
LRU_Rand-16     76.0B ± 0%     36.0B ± 0%   -52.63%  (p=0.000 n=20+20)
LRU_Freq-16     71.0B ± 0%     33.0B ± 0%   -53.52%  (p=0.000 n=19+20)

name         old allocs/op  new allocs/op  delta
2Q_Rand-16       5.00 ± 0%      1.00 ± 0%   -80.00%  (p=0.000 n=20+20)
2Q_Freq-16       5.00 ± 0%      1.00 ± 0%   -80.00%  (p=0.000 n=20+20)
ARC_Rand-16      6.00 ± 0%      1.00 ± 0%   -83.33%  (p=0.000 n=20+20)
ARC_Freq-16      5.00 ± 0%      1.00 ± 0%   -80.00%  (p=0.000 n=20+20)
LRU_Rand-16      3.00 ± 0%      0.00       -100.00%  (p=0.000 n=20+20)
LRU_Freq-16      3.00 ± 0%      0.00       -100.00%  (p=0.000 n=20+20)

[jefferai]

What's the issue with container/list in the first place?

[jefferai]

It seems like Google's btree has never been tagged so they probably didn't want to introduce v2 in order to not have to start tagging it.

I think it's probably fine here to just go v2 and use the generic interface.

I'm still skeptical of the change to an outside container library; currently the library has no outside dependencies and I don't really want to add them. But I also don't know what the issue is.

@SoMuchForSubtlety Are there meaningful differences between your version and what's proposed here, other than the container/list question?

[AskAlexSharov]

What's the issue with container/list in the first place?

it doesn't support generics

[SoMuchForSubtlety]

@SoMuchForSubtlety Are there meaningful differences between your version and what's proposed here, other than the container/list question?

Not really. I kept the naked returns instead of explicitly declaring empty return values for misses, but that's just a style choice.

Here is the benchstat of my code and this PR

$ benchstat pr.txt mine.txt
name         old time/op    new time/op    delta
2Q_Rand-16      587ns ± 9%     516ns ±10%   -12.20%  (p=0.000 n=16+16)
2Q_Freq-16      494ns ±12%     442ns ± 6%   -10.51%  (p=0.000 n=20+17)
ARC_Rand-16     758ns ± 8%     683ns ±10%    -9.90%  (p=0.000 n=20+20)
ARC_Freq-16     619ns ±11%     549ns ±14%   -11.24%  (p=0.000 n=20+20)
LRU_Rand-16     240ns ± 8%     216ns ± 8%   -10.06%  (p=0.000 n=20+20)
LRU_Freq-16     220ns ± 5%     200ns ± 7%    -9.07%  (p=0.000 n=20+20)

name         old alloc/op   new alloc/op   delta
2Q_Rand-16      67.0B ± 0%     67.0B ± 0%      ~     (all equal)
2Q_Freq-16      59.0B ± 0%     59.0B ± 0%      ~     (all equal)
ARC_Rand-16     84.4B ± 1%     84.0B ± 0%    -0.47%  (p=0.002 n=20+19)
ARC_Freq-16     67.9B ± 5%     67.2B ± 6%      ~     (p=0.099 n=20+20)
LRU_Rand-16     36.0B ± 0%     36.0B ± 0%      ~     (all equal)
LRU_Freq-16     33.0B ± 0%     33.0B ± 0%      ~     (all equal)

name         old allocs/op  new allocs/op  delta
2Q_Rand-16       2.00 ± 0%      1.00 ± 0%   -50.00%  (p=0.000 n=20+20)
2Q_Freq-16       2.00 ± 0%      1.00 ± 0%   -50.00%  (p=0.000 n=20+20)
ARC_Rand-16      3.00 ± 0%      1.00 ± 0%   -66.67%  (p=0.000 n=20+20)
ARC_Freq-16      2.00 ± 0%      1.00 ± 0%   -50.00%  (p=0.000 n=20+20)
LRU_Rand-16      1.00 ± 0%      0.00       -100.00%  (p=0.000 n=20+20)
LRU_Freq-16      1.00 ± 0%      0.00       -100.00%  (p=0.000 n=20+20)

[jefferai]

it doesn't support generics

Oh, I assumed it had been modified to do so since @SoMuchForSubtlety said he vendored it :-)

[jefferai]

I kept the naked returns instead of explicitly declaring empty return values for misses, but that's just a style choice.

It isn't :-) An empty object could have been explicitly added to the cache. You can't differentiate between the two if you return empty objects on misses. So your style is more correct. Are you planning on PRing it?

[SoMuchForSubtlety]

Are you planning on PRing it?

Sure, I opened #111

[jefferai]

Closing in favor of #111