So, I was experimenting with LRU caches (where the least-recently-used elements get discarded if the cache is full) and realized I could implement it much more efficiently inside of my Red/Black Tree module, and at almost no extra cost. (well, 16 bytes per tree node, but they were already big)
The short version is that there is now an optional linked list running through the tree nodes in the order of insertion, and you may also omit nodes from that list (if you want them to persist in the cache) and you may re-order the list however you like.
I'm currently using it for marking positions within a log file, where I parse the timestamp at a given address while performing a binary search of the log, and write down the timestamps and addresses in the cache to speed up later seeks. This problem requires a tree so that I can say "what is the timestamp address before and after my desired timestamp", followed by a binary search of the records in that range.
Meanwhile, you can also insert duplicates for things like statistical tracking over time, such as inserting IP addresses who are abusing your system, and then answer queries about how many violations they've had in the cache's time window (maybe causing you to add them to a firewall blacklist), then expire the events individually. Being a tree, you can also sum up the violations for arbitrary subnets in Log(N) time.
My implementation fares rather excellently vs. the other LRU cache implementations benchmarked by the script in Hash::Ordered.
Benchmark code:
$mark{"t:rb:x"}= sub { my $t= Tree::RB::XS->new(compare_fn => 'int', track_recent => 1, lookup_updates_recent => 1, kv => $PAIRS{$size}); }; ... my $t_rb_x= Tree::RB::XS->new(compare_fn => 'int', track_recent => 1, lookup_updates_recent => 1, kv => $PAIRS{$size} ); $mark{"t:rb:x"} = sub { $v = $t_rb_x->get($_) for @lookup } +; ... my $t_rb_x= Tree::RB::XS->new(compare_fn => 'int', track_recent => 1, lookup_updates_recent => 1, kv => $PAIRS{$size} ); $mark{"t:rb:x"} = sub { $t_rb_x->put($_, $new_value) for @look +up }; ... $mark{"t:rb:x"} = sub { my $t_rb_x= Tree::RB::XS->new(compare_fn => 'int', track_recent => 1, lookup_updates_recent => 1); $t_rb_x->put( irand(), 42 ) for 1 .. $n; }; ... $mark{"t:rb:x"} = sub { my $t_rb_x= Tree::RB::XS->new(compare_fn => 'int', track_recent => 1, lookup_updates_recent => 1, kv => $PAIRS{$size} ); $t_rb_x->delete($_) for @lookup; }; ... my $t_rb_x= Tree::RB::XS->new(compare_fn => 'int', track_recent => 1, lookup_updates_recent => 1, kv => $PAIRS{$size} ); $mark{"t:rb:x"} = sub { @list= $t_rb_x->iter->next_kv(9**9) };
Results for ordered hash creation for 10 elements t:rb:x 315676/s t:h:i 304490/s h:o_oo 185403/s * h:o_th 180326/s * a:ah_rf 177953/s a:ah_cp 116599/s t:ix_th 93519/s t:ix_oo 93519/s a:oh 82576/s t:llh 45996/s d:xh_ls 20798/s d:xh_rf 20366/s Results for ordered hash creation for 100 elements t:rb:x 65161/s t:h:i 34008/s a:ah_rf 21719/s h:o_oo 19138/s * h:o_th 18864/s * a:ah_cp 11205/s t:ix_oo 10064/s t:ix_th 9990/s a:oh 9598/s t:llh 4695/s d:xh_ls 2167/s d:xh_rf 2133/s Results for ordered hash creation for 1000 elements t:rb:x 4305/s t:h:i 2314/s a:ah_rf 2142/s h:o_oo 1759/s * h:o_th 1759/s * a:ah_cp 1159/s a:oh 996/s t:ix_th 928/s t:ix_oo 923/s t:llh 422/s d:xh_ls 211/s d:xh_rf 209/s Results for fetching ~10% of 10 elements t:rb:x 4444941/s h:o_oo 3611814/s * t:ix_oo 2079761/s d:xh_oo 1846629/s t:h:i 1695851/s h:o_th 1510215/s * t:ix_th 1104466/s d:xh_rf 1100831/s a:oh 911959/s t:llh 852789/s a:ah 322235/s Results for fetching ~10% of 100 elements t:rb:x 503218/s h:o_oo 436944/s * t:ix_oo 230531/s d:xh_oo 213144/s t:h:i 183444/s h:o_th 164485/s * t:ix_th 118605/s d:xh_rf 113302/s a:oh 97931/s t:llh 87657/s a:ah 33378/s Results for fetching ~10% of 1000 elements t:rb:x 45340/s h:o_oo 42073/s * t:ix_oo 23335/s d:xh_oo 20917/s t:h:i 18336/s h:o_th 16196/s * t:ix_th 11708/s d:xh_rf 11428/s a:oh 9643/s t:llh 8768/s a:ah 3367/s Results for replacing ~10% of 10 elements t:rb:x 4355585/s h:o_oo 2396909/s * t:h:i 1718047/s t:ix_oo 1467562/s d:xh_oo 1250490/s h:o_th 1096501/s * t:llh 960586/s a:oh 846612/s t:ix_th 828653/s d:xh_rf 790392/s a:ah 216507/s Results for replacing ~10% of 100 elements t:rb:x 489652/s h:o_oo 267005/s * t:h:i 184544/s t:ix_oo 155797/s d:xh_oo 137282/s h:o_th 114904/s * t:llh 99553/s a:oh 87495/s t:ix_th 86238/s d:xh_rf 82857/s a:ah 21627/s Results for replacing ~10% of 1000 elements t:rb:x 45080/s h:o_oo 27480/s * t:h:i 18371/s t:ix_oo 15544/s d:xh_oo 14380/s h:o_th 11220/s * t:llh 9972/s a:oh 9049/s t:ix_th 8548/s d:xh_rf 8515/s a:ah 2194/s Results for adding 10 elements to empty hash t:h:i 527278/s h:o_oo 503199/s * t:rb:x 468156/s t:ix_oo 422388/s h:o_th 358066/s * t:ix_th 345994/s t:llh 287424/s a:oh 225832/s a:ah 151480/s d:xh_oo 120301/s d:xh_rf 112564/s Results for adding 100 elements to empty hash t:rb:x 157190/s t:h:i 91380/s h:o_oo 84490/s * t:ix_oo 76030/s h:o_th 57742/s * t:ix_th 55961/s a:oh 50005/s t:llh 41273/s d:xh_oo 32433/s d:xh_rf 28390/s a:ah 19322/s Results for adding 1000 elements to empty hash t:rb:x 19796/s t:h:i 9067/s h:o_oo 8644/s * t:ix_oo 7907/s h:o_th 5920/s * t:ix_th 5855/s a:oh 5574/s t:llh 4091/s d:xh_oo 3885/s d:xh_rf 3297/s a:ah 1802/s Results for creating 10 element hash then deleting ~10% t:rb:x 280833/s t:h:i 255737/s h:o_oo 157289/s * h:o_th 136261/s * a:ah 85743/s t:ix_oo 70952/s a:oh 69817/s t:ix_th 69092/s t:llh 39854/s d:xh_oo 18653/s d:xh_rf 18476/s Results for creating 100 element hash then deleting ~10% t:rb:x 55642/s t:h:i 28087/s h:o_oo 13396/s * h:o_th 12607/s * a:oh 6635/s t:ix_oo 5800/s t:ix_th 5623/s t:llh 4114/s a:ah 3921/s d:xh_oo 1870/s d:xh_rf 1866/s Results for creating 1000 element hash then deleting ~10% t:rb:x 3929/s t:h:i 2441/s h:o_oo 1256/s * h:o_th 1148/s * t:llh 409/s a:oh 215/s d:xh_oo 199/s d:xh_rf 197/s t:ix_th 126/s t:ix_oo 122/s a:ah 53/s Results for listing pairs of 10 element hash a:ah 653473/s t:rb:x 441348/s h:o_oo 324645/s * t:ix_oo 130825/s t:h:i 115922/s h:o_th 78045/s * a:oh 70544/s t:ix_th 68923/s d:xh 55640/s t:llh 53890/s Results for listing pairs of 100 element hash t:rb:x 126519/s a:ah 77020/s h:o_oo 37796/s * t:ix_oo 13246/s t:h:i 11378/s h:o_th 8677/s * a:oh 7528/s t:ix_th 6991/s d:xh 5844/s t:llh 5347/s Results for listing pairs of 1000 element hash t:rb:x 15485/s a:ah 8171/s h:o_oo 3432/s * t:ix_oo 1299/s t:h:i 1120/s h:o_th 827/s * a:oh 702/s t:ix_th 693/s d:xh 577/s t:llh 531/s
In reply to Tree::RB::XS now doubles as a LRU cache by NERDVANA
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |