Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

understanding the performance characteristics of bounded cache #3530

Closed
tirumaraiselvan opened this issue Dec 13, 2019 · 1 comment
Closed

understanding the performance characteristics of bounded cache #3530

tirumaraiselvan opened this issue Dec 13, 2019 · 1 comment
Assignees
@jberryman
Labels
c/server Related to server p/high candidate for being included in the upcoming sprint

Comments

@tirumaraiselvan
Copy link
Contributor

tirumaraiselvan commented Dec 13, 2019 •
edited
Loading

@0x777 said :

What's the difference in metrics like req/s and latency? Does it warrant extra work to improve the data structures used?
@tirumaraiselvan tirumaraiselvan added the c/server Related to server label Dec 13, 2019
@jberryman jberryman mentioned this issue Dec 13, 2019
Merged
jberryman added a commit to jberryman/graphql-engine that referenced this issue Dec 13, 2019
@jberryman
Initial benchmarks for caching. Closes hasura#3530
7adc834 
These aren't suitable e.g. for running in CI since some take far too
long (and an impossibly long-time when running under criterion's normal
bootstrapping sampling regime.

We might try to improve this ourselves:
 haskell/criterion#218

An initial summary analysis will be in hasura#3530.
@jberryman jberryman mentioned this issue Dec 13, 2019
Merged
28 tasks
jberryman added a commit to jberryman/graphql-engine that referenced this issue Dec 13, 2019
@jberryman
Initial benchmarks for caching. Closes hasura#3530
eb9ff22 
These aren't suitable e.g. for running in CI since some take far too
long (and an impossibly long-time when running under criterion's normal
bootstrapping sampling regime.

We might try to improve this ourselves:
 haskell/criterion#218

An initial summary analysis will be in hasura#3530.
@jberryman
Copy link
Collaborator

jberryman commented Dec 16, 2019 •
edited
Loading

@0x777
Here are the raw numbers with some analysis and what I've taken away.

The most interesting parts have little to do with the mechanics of caching per se (overhead of LRU bookkeeping, or insert time), and much more to do with how effective caching is and how the various parameters interact (the "realistic" benchmarks below).

Microbenchmarks

Microbenchmarks of lookups; not very interesting
The unbounded cache performs better at larger sizes, but the cost of a lookup
at the largest supported cache size in Bounded is less than 1us which is not
worth optimizing wrt how we use the cache currently.

benchmarking lookup/size 1/unbounded/hit
time                 218.0 ns   (214.8 ns .. 220.3 ns)
                     0.986 R²   (0.975 R² .. 0.994 R²)
mean                 217.4 ns   (209.9 ns .. 220.6 ns)
std dev              15.24 ns   (5.682 ns .. 29.68 ns)
variance introduced by outliers: 82% (severely inflated)
                                    
benchmarking lookup/size 1/unbounded/miss
time                 50.40 ns   (48.85 ns .. 53.95 ns)
                     0.815 R²   (0.724 R² .. 0.885 R²)
mean                 99.29 ns   (83.16 ns .. 116.7 ns)
std dev              63.75 ns   (58.08 ns .. 65.77 ns)
variance introduced by outliers: 100% (severely inflated)
                                    
benchmarking lookup/size 1/bounded/hit
time                 177.5 ns   (174.1 ns .. 183.3 ns)
                     0.860 R²   (0.790 R² .. 0.916 R²)
mean                 371.7 ns   (312.9 ns .. 433.8 ns)
std dev              241.1 ns   (221.1 ns .. 254.2 ns)
variance introduced by outliers: 100% (severely inflated)
                                    
benchmarking lookup/size 1/bounded/miss
time                 88.74 ns   (88.11 ns .. 89.40 ns)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 88.94 ns   (88.23 ns .. 91.21 ns)
std dev              3.882 ns   (1.212 ns .. 7.907 ns)
variance introduced by outliers: 65% (severely inflated)
                                    
benchmarking lookup/size 100/unbounded/hit
time                 74.35 ns   (73.87 ns .. 74.88 ns)
                     0.999 R²   (0.998 R² .. 1.000 R²)
mean                 74.62 ns   (73.97 ns .. 76.85 ns)
std dev              3.470 ns   (1.210 ns .. 6.912 ns)
variance introduced by outliers: 68% (severely inflated)
                                    
benchmarking lookup/size 100/unbounded/miss
time                 55.43 ns   (54.82 ns .. 56.23 ns)
                     0.998 R²   (0.996 R² .. 0.999 R²)
mean                 56.88 ns   (55.04 ns .. 62.75 ns)
std dev              9.816 ns   (1.437 ns .. 19.80 ns)
variance introduced by outliers: 97% (severely inflated)
                                    
benchmarking lookup/size 100/bounded/hit
time                 408.3 ns   (404.8 ns .. 412.9 ns)
                     0.999 R²   (0.998 R² .. 1.000 R²)
mean                 412.0 ns   (406.5 ns .. 428.3 ns)
std dev              32.43 ns   (7.165 ns .. 60.81 ns)
variance introduced by outliers: 84% (severely inflated)
                                    
benchmarking lookup/size 100/bounded/miss
time                 170.5 ns   (167.7 ns .. 173.4 ns)
                     0.998 R²   (0.997 R² .. 0.999 R²)
mean                 169.3 ns   (167.8 ns .. 172.2 ns)
std dev              6.765 ns   (4.302 ns .. 11.21 ns)
variance introduced by outliers: 59% (severely inflated)
                                    
benchmarking lookup/size 65535/unbounded/hit
time                 231.7 ns   (177.9 ns .. 264.2 ns)
                     0.803 R²   (0.704 R² .. 0.874 R²)
mean                 163.4 ns   (124.8 ns .. 202.8 ns)
std dev              106.8 ns   (86.86 ns .. 115.5 ns)
variance introduced by outliers: 100% (severely inflated)
                                    
benchmarking lookup/size 65535/unbounded/miss
time                 118.2 ns   (83.91 ns .. 152.8 ns)
                     0.697 R²   (0.649 R² .. 0.822 R²)
mean                 88.23 ns   (74.04 ns .. 112.1 ns)
std dev              56.09 ns   (33.93 ns .. 78.00 ns)
variance introduced by outliers: 100% (severely inflated)
                                    
benchmarking lookup/size 65535/bounded/hit
time                 794.1 ns   (787.1 ns .. 804.3 ns)
                     0.999 R²   (0.998 R² .. 1.000 R²)
mean                 792.3 ns   (788.4 ns .. 800.2 ns)
std dev              19.59 ns   (11.76 ns .. 29.41 ns)
variance introduced by outliers: 32% (moderately inflated)
                                    
benchmarking lookup/size 65535/bounded/miss
time                 279.9 ns   (277.5 ns .. 283.3 ns)
                     0.998 R²   (0.995 R² .. 1.000 R²)
mean                 283.6 ns   (279.1 ns .. 296.2 ns)
std dev              24.03 ns   (8.909 ns .. 49.99 ns)
variance introduced by outliers: 87% (severely inflated)

Inserts; mostly fine but evicting is somewhat expensive

benchmarking insert x1000/unbounded 
time                 241.2 μs   (160.7 μs .. 345.3 μs)
                     0.585 R²   (0.537 R² .. 0.746 R²)
mean                 368.8 μs   (291.0 μs .. 457.4 μs)
std dev              222.3 μs   (190.5 μs .. 242.3 μs)
variance introduced by outliers: 99% (severely inflated)
                                    
benchmarking insert x1000/bounded   
time                 816.7 μs   (810.0 μs .. 827.8 μs)
                     0.998 R²   (0.994 R² .. 1.000 R²)
mean                 833.3 μs   (822.4 μs .. 862.1 μs)
std dev              48.05 μs   (21.00 μs .. 89.60 μs)
variance introduced by outliers: 46% (moderately inflated)

Here we can see an evicting insert is on average ~3us which is relatively
costly, but again probably not worth optimizing in the context of the plan
cache:

benchmarking insert x1000/bounded evicting scan
time                 2.716 ms   (2.255 ms .. 3.314 ms)
                     0.874 R²   (0.818 R² .. 0.994 R²)
mean                 2.426 ms   (2.267 ms .. 2.852 ms)
std dev              490.4 μs   (97.44 μs .. 845.0 μs)
variance introduced by outliers: 80% (severely inflated)

"Realistic" benchmarks

Here we do more "realistic" tests of the cache under the assumption that
frequency of values is skewed in a zipf (long tail) distribution (i.e.
where a very small number of values occur disproportionately more frequently).
This is usually a good hypothesis in general but might not be useful for users
who e.g. only make use of parameterized queries, where the cache will stay
very small and presumably be very effective... I'm not sure.

These benchmarks loop over 1-million zipf-distributed values doing:

x <- lookup val
if wasFound x
  then continue
  else do
    someWorkToSimulateCacheMissCost -- this is tunable
    insert val
    continue

These can be used to help determine how different caching/eviction policies
can affect throughput, or judge the effects of optimizing a cache miss. See
the benchmark code for more notes.

NOTES:

  • optimistic distribution: a very highly skewed zipf distribution with many cache hits
  • realistic distribution: something that seems more subjectively realistic, with a longer tail
  • NxCPUs threads: how many threads among which to divide up work, relative to number of HECs

Realistic load, no miss cost

These just measure the latency of the caching machinery itself (as well as
forking and scheduling of threads, etc.) under our realistic workload.

These number are about what we'd expect based on the microbenchmarks above
and it doesn't seem like we've been able to induce any bad blocking.

benchmarking realistic requests x1000000, no miss cost/optimistic distribution/2xCPUs threads/unbounded
time                 567.3 ms   (553.5 ms .. 576.2 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 450.4 ms   (373.6 ms .. 491.4 ms)
std dev              72.89 ms   (23.11 ms .. 94.79 ms)
variance introduced by outliers: 46% (moderately inflated)
                                    
benchmarking realistic requests x1000000, no miss cost/optimistic distribution/2xCPUs threads/bounded effectively unbounded
time                 837.5 ms   (502.9 ms .. 1.001 s)
                     0.982 R²   (0.948 R² .. 1.000 R²)
mean                 867.0 ms   (796.6 ms .. 965.7 ms)
std dev              105.3 ms   (47.26 ms .. 145.9 ms)
variance introduced by outliers: 23% (moderately inflated)
                                    
benchmarking realistic requests x1000000, no miss cost/optimistic distribution/2xCPUs threads/bounded 10pct ideal capacity
time                 904.2 ms   (838.3 ms .. 1.014 s)
                     0.998 R²   (0.996 R² .. 1.000 R²)
mean                 812.8 ms   (762.5 ms .. 846.0 ms)
std dev              51.31 ms   (24.01 ms .. 71.93 ms)
variance introduced by outliers: 19% (moderately inflated)
                                    
benchmarking realistic requests x1000000, no miss cost/optimistic distribution/100xCPUs threads/unbounded
time                 1.462 s    (563.5 ms .. NaN s)
                     0.930 R²   (0.910 R² .. 1.000 R²)
mean                 1.754 s    (1.471 s .. 2.208 s)
std dev              430.8 ms   (997.7 μs .. 525.8 ms)
variance introduced by outliers: 48% (moderately inflated)
                                    
benchmarking realistic requests x1000000, no miss cost/optimistic distribution/100xCPUs threads/bounded effectively unbounded
time                 2.261 s    (1.562 s .. 3.191 s)
                     0.981 R²   (0.945 R² .. 1.000 R²)
mean                 2.486 s    (2.371 s .. 2.700 s)
std dev              209.0 ms   (15.41 ms .. 255.7 ms)
variance introduced by outliers: 22% (moderately inflated)
                                    
benchmarking realistic requests x1000000, no miss cost/optimistic distribution/100xCPUs threads/bounded 10pct ideal capacity
time                 3.021 s    (1.793 s .. 5.051 s)
                     0.952 R²   (0.898 R² .. 1.000 R²)
mean                 2.505 s    (2.293 s .. 2.834 s)
std dev              312.6 ms   (73.26 ms .. 404.0 ms)
variance introduced by outliers: 23% (moderately inflated)
                                    
benchmarking realistic requests x1000000, no miss cost/realistic distribution/2xCPUs threads/unbounded
time                 1.299 s    (NaN s .. 1.678 s)
                     0.975 R²   (0.916 R² .. 1.000 R²)
mean                 1.201 s    (1.062 s .. 1.290 s)
std dev              145.4 ms   (80.96 ms .. 205.0 ms)
variance introduced by outliers: 23% (moderately inflated)
                                    
benchmarking realistic requests x1000000, no miss cost/realistic distribution/2xCPUs threads/bounded maxBound (10pct ideal capacity)
time                 3.135 s    (3.093 s .. 3.203 s)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 3.123 s    (3.112 s .. 3.130 s)
std dev              12.07 ms   (9.288 ms .. 13.77 ms)
variance introduced by outliers: 19% (moderately inflated)
                                    
benchmarking realistic requests x1000000, no miss cost/realistic distribution/2xCPUs threads/bounded 6000 (1pct ideal capacity)
time                 2.535 s    (2.467 s .. 2.648 s)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 2.551 s    (2.528 s .. 2.568 s)
std dev              25.11 ms   (2.740 ms .. 35.39 ms)
variance introduced by outliers: 19% (moderately inflated)
                                    
benchmarking realistic requests x1000000, no miss cost/realistic distribution/100xCPUs threads/unbounded
time                 2.800 s    (1.201 s .. 3.752 s)
                     0.965 R²   (0.883 R² .. 1.000 R²)
mean                 3.167 s    (2.925 s .. 3.320 s)
std dev              234.3 ms   (60.40 ms .. 314.5 ms)
variance introduced by outliers: 21% (moderately inflated)
                                    
benchmarking realistic requests x1000000, no miss cost/realistic distribution/100xCPUs threads/bounded maxBound (10pct ideal capacity)
time                 6.762 s    (6.511 s .. 6.984 s)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 6.488 s    (6.288 s .. 6.610 s)
std dev              189.0 ms   (19.06 ms .. 240.1 ms)
variance introduced by outliers: 19% (moderately inflated)
                                    
benchmarking realistic requests x1000000, no miss cost/realistic distribution/100xCPUs threads/bounded 6000 (1pct ideal capacity)
time                 6.100 s    (3.889 s .. 8.065 s)
                     0.984 R²   (0.942 R² .. 1.000 R²)
mean                 6.087 s    (5.695 s .. 6.566 s)
std dev              539.3 ms   (180.1 ms .. 724.7 ms)
variance introduced by outliers: 22% (moderately inflated)

Realistic load, with a realistic cost of a cache miss

(The format here is different because these were too slow to run with
criterion; see benchmarks code. HITS/MISSES are per-thread cache
(hit,miss) counts)

benchmarking realistic requests x1000000, real plan gen cost/optimistic distribution/2xCPUs threads/unbounded
HITS/MISSES: [(105497,5615),(105611,5500),(105485,5626),(107335,3776),(107194,3917),(107241,3870),(107333,3778),(107143,3968),(107069,4042)]
TIMING:  264,285 ms

benchmarking realistic requests x1000000, real plan gen cost/optimistic distribution/2xCPUs threads/bounded effectively unbounded
HITS/MISSES: [(105497,5615),(105611,5500),(105485,5626),(107201,3910),(107276,3835),(107312,3799),(107136,3975),(107371,3740),(107076,4035)]
TIMING:  262,234 ms

benchmarking realistic requests x1000000, real plan gen cost/optimistic distribution/2xCPUs threads/bounded 10pct ideal capacity
HITS/MISSES: [(104998,6114),(105100,6011),(104935,6176),(105637,5474),(105438,5673),(105589,5522),(105671,5440),(105667,5444),(105575,5536)]
TIMING:  366,378 ms

benchmarking realistic requests x1000000, real plan gen cost/optimistic distribution/100xCPUs threads/unbounded
HITS/MISSES: [(2110,384),(2125,369),(2123,371),(2414,80),(2346,148),(2287,207),(2275,219),(2295,199),(2277,217),(2349,145),(2327,167),(2335,159),(2319,175),(2329,165),(2322,172),(2332,162),(2324,170),(2343,151),(2332,162),(2327,167),(2330,164),(2321,173),(2345,149),(2340,154),(2358,136),(2352,142),(2339,155),(2303,191),(2308,186),(2326,168),(2323,171),(2325,169),(2288,206),(2289,205),(2303,191),(2311,183),(2320,174),(2340,154),(2364,130),(2364,130),(2359,135),(2363,131),(2370,124),(2381,113),(2364,130),(2388,106),(2368,126),(2363,131),(2350,144),(2354,140),(2358,136),(2356,138),(2368,126),(2352,142),(2353,141),(2368,126),(2355,139),(2358,136),(2349,145),(2355,139),(2378,116),(2344,150),(2365,129),(2376,118),(2360,134),(2336,158),(2362,132),(2356,138),(2359,135),(2360,134),(2369,125),(2360,134),(2358,136),(2374,120),(2346,148),(2369,125),(2358,136),(2358,136),(2382,112),(2385,109),(2384,110),(2389,105),(2394,100),(2372,122),(2376,118),(2375,119),(2387,107),(2381,113),(2394,100),(2380,114),(2374,120),(2374,120),(2385,109),(2387,107),(2382,112),(2368,126),(2388,106),(2373,121),(2381,113),(2378,116),(2409,85),(2391,103),(2395,99),(2378,116),(2383,111),(2381,113),(2390,104),(2381,113),(2385,109),(2381,113),(2377,117),(2377,117),(2374,120),(2396,98),(2387,107),(2392,102),(2404,90),(2390,104),(2391,103),(2389,105),(2390,104),(2403,91),(2405,89),(2407,87),(2392,102),(2400,94),(2384,110),(2385,109),(2387,107),(2401,93),(2376,118),(2383,111),(2395,99),(2398,96),(2390,104),(2408,86),(2403,91),(2394,100),(2386,108),(2379,115),(2387,107),(2390,104),(2403,91),(2383,111),(2391,103),(2407,87),(2402,92),(2396,98),(2392,102),(2395,99),(2390,104),(2399,95),(2392,102),(2392,102),(2392,102),(2395,99),(2401,93),(2375,119),(2402,92),(2390,104),(2382,112),(2409,85),(2409,85),(2386,108),(2402,92),(2404,90),(2419,75),(2397,97),(2395,99),(2410,84),(2407,87),(2398,96),(2411,83),(2412,82),(2403,91),(2409,85),(2413,81),(2396,98),(2402,92),(2400,94),(2397,97),(2411,83),(2381,113),(2392,102),(2413,81),(2402,92),(2403,91),(2393,101),(2393,101),(2399,95),(2397,97),(2392,102),(2416,78),(2415,79),(2421,73),(2416,78),(2411,83),(2398,96),(2402,92),(2424,70),(2411,83),(2419,75),(2412,82),(2410,84),(2418,76),(2406,88),(2407,87),(2411,83),(2409,85),(2421,73),(2401,93),(2411,83),(2416,78),(2403,91),(2426,68),(2411,83),(2397,97),(2404,90),(2397,97),(2395,99),(2427,67),(2410,84),(2394,100),(2419,75),(2408,86),(2419,75),(2399,95),(2429,65),(2397,97),(2398,96),(2413,81),(2404,90),(2410,84),(2405,89),(2391,103),(2406,88),(2398,96),(2412,82),(2400,94),(2402,92),(2438,56),(2420,74),(2428,66),(2406,88),(2409,85),(2419,75),(2417,77),(2412,82),(2389,105),(2417,77),(2425,69),(2408,86),(2397,97),(2406,88),(2404,90),(2410,84),(2423,71),(2408,86),(2420,74),(2418,76),(2425,69),(2415,79),(2415,79),(2425,69),(2415,79),(2415,79),(2422,72),(2421,73),(2418,76),(2403,91),(2412,82),(2415,79),(2417,77),(2411,83),(2417,77),(2425,69),(2406,88),(2410,84),(2421,73),(2419,75),(2415,79),(2420,74),(2427,67),(2409,85),(2423,71),(2419,75),(2431,63),(2420,74),(2415,79),(2407,87),(2420,74),(2414,80),(2411,83),(2413,81),(2396,98),(2419,75),(2414,80),(2408,86),(2410,84),(2405,89),(2427,67),(2390,104),(2420,74),(2420,74),(2415,79),(2412,82),(2419,75),(2423,70),(2406,87),(2419,74),(2426,67),(2427,66),(2410,83),(2411,82),(2420,73),(2421,72),(2411,82),(2434,59),(2409,84),(2399,94),(2407,86),(2404,89),(2418,75),(2418,75),(2418,75),(2426,67),(2431,62),(2425,68),(2422,71),(2414,79),(2415,78),(2436,57),(2414,79),(2416,77),(2433,60),(2427,66),(2420,73),(2421,72),(2413,80),(2411,82),(2413,80),(2413,80),(2416,77),(2431,62),(2423,70),(2417,76),(2426,67),(2424,69),(2419,74),(2405,88),(2433,60),(2435,58),(2401,92),(2418,75),(2417,76),(2419,74),(2416,77),(2421,72),(2419,74),(2420,73),(2420,73),(2415,78),(2420,73),(2419,74),(2423,70),(2407,86),(2420,73),(2410,83),(2423,70),(2427,66),(2414,79),(2417,76),(2422,71),(2419,74),(2428,65),(2426,67),(2414,79),(2396,97),(2424,69),(2427,66),(2394,99),(2419,74),(2418,75),(2414,79),(2419,74),(2419,74),(2425,68),(2432,61),(2406,87),(2436,57),(2417,76),(2403,90),(2414,79),(2430,63),(2402,91),(2432,61),(2430,63),(2429,64),(2417,76),(2407,86),(2429,64)]
TIMING:  295,274 ms

benchmarking realistic requests x1000000, real plan gen cost/optimistic distribution/100xCPUs threads/bounded effectively unbounded
HITS/MISSES: [(2110,384),(2125,369),(2123,371),(2408,86),(2370,124),(2384,110),(2254,240),(2287,207),(2267,227),(2311,183),(2292,202),(2305,189),(2284,210),(2303,191),(2284,210),(2300,194),(2298,196),(2307,187),(2266,228),(2261,233),(2274,220),(2280,214),(2398,96),(2388,106),(2407,87),(2403,91),(2392,102),(2387,107),(2363,131),(2400,94),(2384,110),(2402,92),(2380,114),(2374,120),(2365,129),(2380,114),(2403,91),(2419,75),(2392,102),(2375,119),(2385,109),(2357,137),(2401,93),(2418,76),(2382,112),(2396,98),(2395,99),(2412,82),(2400,94),(2376,118),(2401,93),(2390,104),(2397,97),(2411,83),(2375,119),(2422,72),(2402,92),(2404,90),(2402,92),(2415,79),(2422,72),(2396,98),(2415,79),(2412,82),(2381,113),(2387,107),(2414,80),(2344,150),(2408,86),(2405,89),(2409,85),(2415,79),(2416,78),(2380,114),(2386,108),(2409,85),(2395,99),(2379,115),(2388,106),(2398,96),(2419,75),(2411,83),(2420,74),(2382,112),(2392,102),(2388,106),(2413,81),(2421,73),(2421,73),(2414,80),(2410,84),(2404,90),(2415,79),(2414,80),(2401,93),(2386,108),(2399,95),(2359,135),(2413,81),(2403,91),(2428,66),(2410,84),(2416,78),(2359,135),(2409,85),(2418,76),(2417,77),(2397,97),(2407,87),(2410,84),(2406,88),(2398,96),(2405,89),(2417,77),(2366,128),(2419,75),(2389,105),(2410,84),(2400,94),(2414,80),(2398,96),(2409,85),(2428,66),(2425,69),(2406,88),(2416,78),(2388,106),(2407,87),(2412,82),(2425,69),(2410,84),(2382,112),(2384,110),(2409,85),(2378,116),(2421,73),(2418,76),(2377,117),(2414,80),(2380,114),(2405,89),(2371,123),(2428,66),(2369,125),(2410,84),(2404,90),(2407,87),(2401,93),(2398,96),(2417,77),(2357,137),(2399,95),(2404,90),(2409,85),(2355,139),(2407,87),(2419,75),(2407,87),(2412,82),(2339,155),(2403,91),(2424,70),(2421,73),(2402,92),(2391,103),(2422,72),(2380,114),(2400,94),(2398,96),(2418,76),(2414,80),(2393,101),(2389,105),(2393,101),(2345,149),(2414,80),(2423,71),(2409,85),(2410,84),(2412,82),(2405,89),(2418,76),(2391,103),(2343,151),(2350,144),(2389,105),(2399,95),(2399,95),(2393,101),(2408,86),(2410,84),(2326,168),(2347,147),(2409,85),(2421,73),(2377,117),(2398,96),(2401,93),(2402,92),(2425,69),(2407,87),(2411,83),(2399,95),(2401,93),(2406,88),(2408,86),(2399,95),(2400,94),(2414,80),(2426,68),(2415,79),(2406,88),(2413,81),(2385,109),(2409,85),(2402,92),(2394,100),(2349,145),(2369,125),(2373,121),(2424,70),(2408,86),(2397,97),(2424,70),(2410,84),(2415,79),(2378,116),(2394,100),(2401,93),(2410,84),(2396,98),(2381,113),(2409,85),(2397,97),(2372,122),(2386,108),(2409,85),(2385,109),(2387,107),(2395,99),(2429,65),(2404,90),(2415,79),(2398,96),(2411,83),(2418,76),(2402,92),(2379,115),(2377,117),(2417,77),(2394,100),(2419,75),(2380,114),(2407,87),(2381,113),(2406,88),(2423,71),(2390,104),(2360,134),(2419,75),(2417,77),(2405,89),(2399,95),(2411,83),(2375,119),(2413,81),(2417,77),(2414,80),(2422,72),(2377,117),(2409,85),(2358,136),(2389,105),(2400,94),(2404,90),(2376,118),(2381,113),(2402,92),(2415,79),(2421,73),(2405,89),(2414,80),(2427,67),(2405,89),(2417,77),(2411,83),(2430,64),(2389,105),(2414,80),(2392,102),(2405,89),(2407,87),(2368,126),(2400,94),(2353,141),(2418,76),(2404,90),(2400,94),(2412,82),(2401,93),(2410,84),(2384,110),(2395,99),(2417,77),(2413,81),(2405,89),(2359,135),(2422,71),(2406,87),(2411,82),(2426,67),(2398,95),(2381,112),(2412,81),(2417,76),(2414,79),(2397,96),(2428,65),(2398,95),(2383,110),(2369,124),(2384,109),(2353,140),(2365,128),(2415,78),(2389,104),(2430,63),(2417,76),(2412,81),(2402,91),(2395,98),(2425,68),(2409,84),(2417,76),(2426,67),(2413,80),(2404,89),(2419,74),(2396,97),(2389,104),(2390,103),(2409,84),(2422,71),(2398,95),(2396,97),(2413,80),(2429,64),(2417,76),(2406,87),(2388,105),(2423,70),(2422,71),(2382,111),(2411,82),(2397,96),(2409,84),(2390,103),(2411,82),(2416,77),(2423,70),(2416,77),(2401,92),(2402,91),(2376,117),(2411,82),(2405,88),(2420,73),(2391,102),(2383,110),(2413,80),(2367,126),(2394,99),(2414,79),(2416,77),(2424,69),(2423,70),(2396,97),(2404,89),(2422,71),(2403,90),(2377,116),(2404,89),(2408,85),(2417,76),(2401,92),(2378,115),(2335,158),(2350,143),(2381,112),(2425,68),(2406,87),(2388,105),(2406,87),(2417,76),(2408,85),(2406,87),(2417,76),(2362,131),(2363,130),(2403,90),(2422,71)]
TIMING:  269,417 ms

benchmarking realistic requests x1000000, real plan gen cost/optimistic distribution/100xCPUs threads/bounded 10pct ideal capacity
HITS/MISSES: [(2110,384),(2125,369),(2123,371),(2378,116),(2348,146),(2337,157),(2342,152),(2357,137),(2353,141),(2290,204),(2280,214),(2304,190),(2281,213),(2302,192),(2284,210),(2295,199),(2288,206),(2304,190),(2302,192),(2252,242),(2264,230),(2269,225),(2300,194),(2298,196),(2310,184),(2372,122),(2352,142),(2374,120),(2357,137),(2362,132),(2364,130),(2366,128),(2333,161),(2338,156),(2344,150),(2364,130),(2367,127),(2373,121),(2356,138),(2355,139),(2351,143),(2359,135),(2350,144),(2381,113),(2368,126),(2377,117),(2339,155),(2375,119),(2355,139),(2382,112),(2360,134),(2349,145),(2374,120),(2376,118),(2356,138),(2389,105),(2366,128),(2369,125),(2365,129),(2364,130),(2371,123),(2353,141),(2380,114),(2390,104),(2376,118),(2339,155),(2371,123),(2368,126),(2366,128),(2362,132),(2372,122),(2372,122),(2365,129),(2379,115),(2361,133),(2373,121),(2361,133),(2370,124),(2382,112),(2387,107),(2379,115),(2385,109),(2393,101),(2367,127),(2365,129),(2371,123),(2390,104),(2386,108),(2391,103),(2373,121),(2375,119),(2378,116),(2371,123),(2387,107),(2377,117),(2365,129),(2381,113),(2358,136),(2376,118),(2369,125),(2409,85),(2378,116),(2381,113),(2363,131),(2363,131),(2372,122),(2389,105),(2382,112),(2372,122),(2356,138),(2374,120),(2367,127),(2364,130),(2383,111),(2362,132),(2377,117),(2385,109),(2372,122),(2373,121),(2368,126),(2364,130),(2380,114),(2385,109),(2388,106),(2369,125),(2384,110),(2367,127),(2372,122),(2374,120),(2383,111),(2362,132),(2374,120),(2376,118),(2371,123),(2368,126),(2390,104),(2389,105),(2368,126),(2371,123),(2353,141),(2370,124),(2373,121),(2388,106),(2367,127),(2361,133),(2376,118),(2379,115),(2382,112),(2358,136),(2365,129),(2363,131),(2370,124),(2363,131),(2369,125),(2377,117),(2371,123),(2378,116),(2369,125),(2381,113),(2364,130),(2363,131),(2388,106),(2384,110),(2363,131),(2366,128),(2378,116),(2370,124),(2372,122),(2362,132),(2379,115),(2374,120),(2368,126),(2383,111),(2360,134),(2379,115),(2379,115),(2385,109),(2369,125),(2371,123),(2376,118),(2358,136),(2353,141),(2355,139),(2355,139),(2380,114),(2368,126),(2370,124),(2352,142),(2357,137),(2379,115),(2360,134),(2356,138),(2385,109),(2386,108),(2362,132),(2384,110),(2378,116),(2357,137),(2359,135),(2385,109),(2378,116),(2379,115),(2368,126),(2377,117),(2377,117),(2371,123),(2381,113),(2383,111),(2328,166),(2380,114),(2353,141),(2389,105),(2385,109),(2379,115),(2383,111),(2374,120),(2367,127),(2363,131),(2361,133),(2367,127),(2382,112),(2385,109),(2366,128),(2383,111),(2369,125),(2386,108),(2367,127),(2390,104),(2363,131),(2360,134),(2384,110),(2363,131),(2372,122),(2365,129),(2363,131),(2374,120),(2353,141),(2370,124),(2366,128),(2377,117),(2391,103),(2375,119),(2390,104),(2356,138),(2378,116),(2383,111),(2386,108),(2365,129),(2349,145),(2374,120),(2376,118),(2371,123),(2359,135),(2365,129),(2371,123),(2370,124),(2379,115),(2363,131),(2384,110),(2371,123),(2387,107),(2377,117),(2380,114),(2389,105),(2369,125),(2342,152),(2372,122),(2386,108),(2373,121),(2358,136),(2368,126),(2384,110),(2380,114),(2380,114),(2372,122),(2393,101),(2377,117),(2373,121),(2378,116),(2380,114),(2366,128),(2375,119),(2383,111),(2369,125),(2388,106),(2360,134),(2386,108),(2375,119),(2369,125),(2370,124),(2378,116),(2363,131),(2375,119),(2365,129),(2360,134),(2374,120),(2369,125),(2367,127),(2372,122),(2368,126),(2381,113),(2334,160),(2374,120),(2374,120),(2375,119),(2378,116),(2366,128),(2382,111),(2345,148),(2362,131),(2389,104),(2380,113),(2378,115),(2353,140),(2362,131),(2380,113),(2367,126),(2397,96),(2369,124),(2354,139),(2348,145),(2351,142),(2329,164),(2372,121),(2368,125),(2382,111),(2392,101),(2377,116),(2370,123),(2359,134),(2371,122),(2382,111),(2379,114),(2378,115),(2385,108),(2376,117),(2356,137),(2371,122),(2352,141),(2372,121),(2374,119),(2373,120),(2374,119),(2375,118),(2387,106),(2374,119),(2395,98),(2376,117),(2374,119),(2370,123),(2380,113),(2388,105),(2370,123),(2368,125),(2363,130),(2376,117),(2365,128),(2382,111),(2373,120),(2375,118),(2366,127),(2366,127),(2385,108),(2369,124),(2380,113),(2356,137),(2371,122),(2367,126),(2372,121),(2374,119),(2371,122),(2373,120),(2382,111),(2368,125),(2371,122),(2390,103),(2358,135),(2338,155),(2392,101),(2379,114),(2344,149),(2338,155),(2369,124),(2375,118),(2374,119),(2381,112),(2378,115),(2371,122),(2354,139),(2393,100),(2354,139),(2352,141),(2378,115),(2369,124),(2331,162),(2374,119),(2376,117),(2367,126),(2374,119),(2366,127),(2382,111)]
TIMING:  319,457 ms

benchmarking realistic requests x1000000, real plan gen cost/realistic distribution/2xCPUs threads/unbounded
HITS/MISSES: [(29248,81864),(29267,81844),(29041,82070),(33462,77649),(33958,77153),(34059,77052),(33601,77510),(34111,77000),(34157,76954)]
TIMING: 4,334,676 ms

benchmarking realistic requests x1000000, real plan gen cost/realistic distribution/2xCPUs threads/bounded maxBound (10pct ideal capacity)
HITS/MISSES: [(29248,81864),(29267,81844),(29041,82070),(34065,77046),(33338,77773),(34046,77065),(34221,76890),(33558,77553),(34196,76915)]
TIMING: 4,976,494 ms

benchmarking realistic requests x1000000, real plan gen cost/realistic distribution/2xCPUs threads/bounded 6000 (1pct ideal capacity)
HITS/MISSES: [(22261,88851),(22384,88727),(22120,88991),(22476,88635),(22547,88564),(22427,88684),(22628,88483),(22640,88471),(22536,88575)]
TIMING: 4,907,152 ms

benchmarking realistic requests x1000000, real plan gen cost/realistic distribution/100xCPUs threads/unbounded
HITS/MISSES: [(309,2185),(319,2175),(348,2146),(761,1733),(726,1768),(736,1758),(747,1747),(704,1790),(734,1760),(739,1755),(746,1748),(577,1917),(601,1893),(574,1920),(548,1946),(572,1922),(592,1902),(564,1930),(592,1902),(582,1912),(562,1932),(525,1969),(565,1929),(529,1965),(562,1932),(562,1932),(541,1953),(557,1937),(564,1930),(481,2013),(505,1989),(543,1951),(544,1950),(539,1955),(559,1935),(540,1954),(560,1934),(558,1936),(548,1946),(553,1941),(619,1875),(588,1906),(608,1886),(581,1913),(596,1898),(552,1942),(637,1857),(579,1915),(547,1947),(745,1749),(764,1730),(748,1746),(737,1757),(761,1733),(710,1784),(758,1736),(769,1725),(737,1757),(775,1719),(739,1755),(697,1797),(776,1718),(754,1740),(748,1746),(749,1745),(747,1747),(722,1772),(756,1738),(755,1739),(776,1718),(748,1746),(780,1714),(746,1748),(724,1770),(740,1754),(761,1733),(747,1747),(711,1783),(726,1768),(740,1754),(752,1742),(771,1723),(768,1726),(743,1751),(741,1753),(716,1778),(784,1710),(727,1767),(733,1761),(716,1778),(767,1727),(725,1769),(760,1734),(786,1708),(762,1732),(748,1746),(761,1733),(739,1755),(765,1729),(768,1726),(791,1703),(796,1698),(735,1759),(805,1689),(735,1759),(732,1762),(699,1795),(679,1815),(684,1810),(681,1813),(708,1786),(666,1828),(702,1792),(683,1811),(657,1837),(679,1815),(688,1806),(666,1828),(652,1842),(697,1797),(675,1819),(683,1811),(683,1811),(702,1792),(740,1754),(699,1795),(737,1757),(715,1779),(725,1769),(750,1744),(723,1771),(682,1812),(736,1758),(724,1770),(740,1754),(709,1785),(702,1792),(733,1761),(714,1780),(723,1771),(745,1749),(718,1776),(764,1730),(708,1786),(732,1762),(761,1733),(726,1768),(726,1768),(725,1769),(735,1759),(730,1764),(750,1744),(708,1786),(714,1780),(742,1752),(740,1754),(699,1795),(762,1732),(697,1797),(721,1773),(719,1775),(714,1780),(706,1788),(704,1790),(718,1776),(730,1764),(723,1771),(762,1732),(726,1768),(722,1772),(687,1807),(711,1783),(716,1778),(726,1768),(710,1784),(722,1772),(704,1790),(705,1789),(734,1760),(678,1816),(753,1741),(738,1756),(742,1752),(738,1756),(747,1747),(776,1718),(668,1826),(702,1792),(704,1790),(734,1760),(672,1822),(709,1785),(666,1828),(693,1801),(691,1803),(687,1807),(688,1806),(674,1820),(676,1818),(685,1809),(718,1776),(668,1826),(694,1800),(691,1803),(658,1836),(660,1834),(698,1796),(668,1826),(683,1811),(680,1814),(698,1796),(707,1787),(709,1785),(709,1785),(727,1767),(690,1804),(719,1775),(676,1818),(674,1820),(705,1789),(685,1809),(639,1855),(727,1767),(691,1803),(688,1806),(724,1770),(709,1785),(653,1841),(657,1837),(758,1736),(762,1732),(755,1739),(780,1714),(759,1735),(756,1738),(798,1696),(746,1748),(794,1700),(762,1732),(758,1736),(763,1731),(794,1700),(801,1693),(743,1751),(764,1730),(757,1737),(742,1752),(753,1741),(753,1741),(810,1684),(740,1754),(786,1708),(741,1753),(755,1739),(808,1686),(726,1768),(763,1731),(785,1709),(787,1707),(728,1766),(781,1713),(800,1694),(760,1734),(777,1717),(807,1687),(754,1740),(809,1685),(785,1709),(811,1683),(782,1712),(767,1727),(743,1751),(767,1727),(768,1726),(732,1762),(792,1702),(785,1709),(819,1675),(731,1763),(768,1726),(749,1745),(795,1699),(754,1740),(819,1675),(746,1748),(834,1660),(821,1673),(779,1715),(783,1711),(796,1698),(765,1729),(819,1675),(786,1708),(796,1698),(749,1745),(777,1717),(793,1701),(760,1734),(782,1712),(798,1696),(778,1716),(761,1733),(789,1705),(798,1696),(808,1686),(778,1716),(761,1733),(763,1730),(778,1715),(793,1700),(780,1713),(803,1690),(765,1728),(786,1707),(796,1697),(773,1720),(788,1705),(788,1705),(740,1753),(798,1695),(775,1718),(767,1726),(761,1732),(778,1715),(759,1734),(781,1712),(748,1745),(766,1727),(759,1734),(774,1719),(747,1746),(772,1721),(829,1664),(779,1714),(750,1743),(800,1693),(798,1695),(793,1700),(802,1691),(771,1722),(772,1721),(783,1710),(777,1716),(745,1748),(735,1758),(750,1743),(760,1733),(761,1732),(753,1740),(714,1779),(742,1751),(801,1692),(795,1698),(759,1734),(794,1699),(754,1739),(797,1696),(770,1723),(748,1745),(752,1741),(786,1707),(778,1715),(733,1760),(780,1713),(742,1751),(781,1712),(740,1753),(801,1692),(761,1732),(770,1723),(778,1715),(756,1737),(758,1735),(761,1732),(786,1707),(755,1738),(782,1711),(832,1661),(777,1716),(765,1728),(768,1725),(739,1754),(827,1666),(802,1691),(767,1726),(770,1723),(785,1708),(736,1757),(765,1728),(766,1727),(747,1746),(747,1746),(734,1759),(814,1679),(727,1766),(786,1707),(792,1701),(773,1720),(789,1704),(816,1677),(733,1760)]
TIMING: 4,349,744 ms

benchmarking realistic requests x1000000, real plan gen cost/realistic distribution/100xCPUs threads/bounded maxBound (10pct ideal capacity)
HITS/MISSES: [(309,2185),(319,2175),(348,2146),(623,1871),(625,1869),(667,1827),(683,1811),(619,1875),(631,1863),(630,1864),(659,1835),(610,1884),(661,1833),(649,1845),(614,1880),(616,1878),(636,1858),(627,1867),(630,1864),(630,1864),(529,1965),(638,1856),(670,1824),(629,1865),(647,1847),(679,1815),(552,1942),(554,1940),(663,1831),(517,1977),(520,1974),(625,1869),(544,1950),(552,1942),(554,1940),(762,1732),(765,1729),(719,1775),(698,1796),(547,1947),(675,1819),(653,1841),(678,1816),(627,1867),(674,1820),(670,1824),(685,1809),(644,1850),(599,1895),(657,1837),(588,1906),(655,1839),(631,1863),(662,1832),(521,1973),(668,1826),(675,1819),(554,1940),(553,1941),(678,1816),(542,1952),(583,1911),(578,1916),(685,1809),(568,1926),(537,1957),(740,1754),(554,1940),(551,1943),(785,1709),(761,1733),(709,1785),(755,1739),(725,1769),(742,1752),(755,1739),(734,1760),(716,1778),(758,1736),(745,1749),(759,1735),(795,1699),(797,1697),(775,1719),(772,1722),(711,1783),(814,1680),(644,1850),(751,1743),(688,1806),(772,1722),(761,1733),(782,1712),(781,1713),(708,1786),(757,1737),(709,1785),(701,1793),(747,1747),(743,1751),(810,1684),(790,1704),(749,1745),(789,1705),(709,1785),(701,1793),(789,1705),(711,1783),(755,1739),(746,1748),(761,1733),(758,1736),(789,1705),(728,1766),(622,1872),(756,1738),(725,1769),(701,1793),(732,1762),(768,1726),(760,1734),(773,1721),(773,1721),(763,1731),(802,1692),(759,1735),(750,1744),(755,1739),(745,1749),(812,1682),(716,1778),(749,1745),(798,1696),(775,1719),(785,1709),(762,1732),(753,1741),(770,1724),(724,1770),(632,1862),(809,1685),(622,1872),(703,1791),(771,1723),(770,1724),(782,1712),(714,1780),(729,1765),(727,1767),(785,1709),(785,1709),(805,1689),(759,1735),(733,1761),(798,1696),(802,1692),(760,1734),(825,1669),(686,1808),(754,1740),(693,1801),(758,1736),(736,1758),(741,1753),(710,1784),(727,1767),(784,1710),(826,1668),(785,1709),(751,1743),(739,1755),(759,1735),(755,1739),(756,1738),(732,1762),(785,1709),(753,1741),(775,1719),(722,1772),(668,1826),(752,1742),(763,1731),(793,1701),(770,1724),(750,1744),(823,1671),(725,1769),(777,1717),(757,1737),(696,1798),(763,1731),(793,1701),(741,1753),(745,1749),(778,1716),(723,1771),(765,1729),(757,1737),(749,1745),(786,1708),(774,1720),(731,1763),(726,1768),(754,1740),(677,1817),(709,1785),(731,1763),(639,1855),(767,1727),(726,1768),(771,1723),(764,1730),(797,1697),(771,1723),(794,1700),(663,1831),(801,1693),(724,1770),(712,1782),(799,1695),(751,1743),(720,1774),(775,1719),(731,1763),(756,1738),(780,1714),(651,1843),(638,1856),(721,1773),(730,1764),(769,1725),(723,1771),(789,1705),(737,1757),(755,1739),(807,1687),(754,1740),(755,1739),(764,1730),(753,1741),(781,1713),(744,1750),(793,1701),(713,1781),(764,1730),(622,1872),(749,1745),(771,1723),(621,1873),(804,1690),(729,1765),(790,1704),(656,1838),(629,1865),(806,1688),(731,1763),(666,1828),(791,1703),(758,1736),(746,1748),(691,1803),(759,1735),(755,1739),(776,1718),(707,1787),(746,1748),(802,1692),(757,1737),(765,1729),(774,1720),(730,1764),(738,1756),(767,1727),(780,1714),(756,1738),(746,1748),(787,1707),(826,1668),(730,1764),(771,1723),(752,1742),(779,1715),(713,1781),(823,1671),(640,1854),(702,1792),(768,1726),(792,1702),(725,1769),(645,1849),(746,1748),(763,1731),(750,1744),(706,1788),(674,1820),(769,1725),(791,1703),(777,1717),(747,1747),(801,1693),(760,1734),(758,1736),(782,1712),(793,1701),(787,1707),(779,1715),(730,1764),(755,1738),(774,1719),(732,1761),(788,1705),(721,1772),(759,1734),(786,1707),(795,1698),(714,1779),(779,1714),(798,1695),(734,1759),(791,1702),(782,1711),(793,1700),(770,1723),(766,1727),(750,1743),(772,1721),(755,1738),(711,1782),(767,1726),(788,1705),(695,1798),(752,1741),(822,1671),(769,1724),(771,1722),(805,1688),(740,1753),(781,1712),(801,1692),(784,1709),(761,1732),(795,1698),(741,1752),(753,1740),(749,1744),(746,1747),(746,1747),(611,1882),(666,1827),(711,1782),(759,1734),(782,1711),(797,1696),(632,1861),(800,1693),(682,1811),(786,1707),(644,1849),(760,1733),(611,1882),(700,1793),(723,1770),(719,1774),(733,1760),(723,1770),(742,1751),(680,1813),(802,1691),(748,1745),(756,1737),(737,1756),(706,1787),(772,1721),(752,1741),(732,1761),(735,1758),(753,1740),(842,1651),(738,1755),(671,1822),(776,1717),(743,1750),(842,1651),(760,1733),(703,1790),(715,1778),(795,1698),(686,1807),(748,1745),(716,1777),(734,1759),(695,1798),(742,1751),(788,1705),(763,1730),(773,1720),(804,1689),(712,1781),(729,1764),(824,1669),(740,1753)]
TIMING: 4,342,820 ms

benchmarking realistic requests x1000000, real plan gen cost/realistic distribution/100xCPUs threads/bounded 6000 (1pct ideal capacity)
HITS/MISSES: [(309,2185),(319,2175),(348,2146),(488,2006),(476,2018),(513,1981),(512,1982),(473,2021),(483,2011),(473,2021),(499,1995),(486,2008),(498,1996),(501,1993),(454,2040),(497,1997),(516,1978),(504,1990),(490,2004),(502,1992),(480,2014),(470,2024),(510,1984),(469,2025),(513,1981),(513,1981),(488,2006),(510,1984),(521,1973),(446,2048),(468,2026),(492,2002),(483,2011),(495,1999),(497,1997),(495,1999),(518,1976),(504,1990),(502,1992),(485,2009),(526,1968),(505,1989),(535,1959),(487,2007),(514,1980),(456,2038),(552,1942),(499,1995),(461,2033),(504,1990),(527,1967),(490,2004),(486,2008),(529,1965),(465,2029),(517,1977),(547,1947),(514,1980),(525,1969),(520,1974),(490,2004),(541,1953),(519,1975),(507,1987),(509,1985),(502,1992),(502,1992),(492,2002),(515,1979),(501,1993),(501,1993),(524,1970),(492,2002),(470,2024),(493,2001),(504,1990),(527,1967),(466,2028),(492,2002),(491,2003),(526,1968),(511,1983),(523,1971),(510,1984),(482,2012),(466,2028),(523,1971),(477,2017),(474,2020),(484,2010),(501,1993),(487,2007),(497,1997),(535,1959),(528,1966),(484,2010),(510,1984),(502,1992),(528,1966),(510,1984),(544,1950),(533,1961),(480,2014),(547,1947),(501,1993),(486,2008),(521,1973),(512,1982),(500,1994),(502,1992),(528,1966),(489,2005),(512,1982),(507,1987),(478,2016),(491,2003),(517,1977),(502,1992),(471,2023),(485,2009),(494,2000),(516,1978),(496,1998),(521,1973),(534,1960),(499,1995),(538,1956),(512,1982),(531,1963),(536,1958),(519,1975),(469,2025),(516,1978),(530,1964),(523,1971),(473,2021),(492,2002),(513,1981),(514,1980),(512,1982),(556,1938),(493,2001),(527,1967),(491,2003),(518,1976),(538,1956),(510,1984),(497,1997),(511,1983),(514,1980),(520,1974),(543,1951),(492,2002),(497,1997),(512,1982),(525,1969),(490,2004),(557,1937),(495,1999),(504,1990),(491,2003),(537,1957),(485,2009),(491,2003),(503,1991),(497,1997),(495,1999),(532,1962),(511,1983),(511,1983),(488,2006),(499,1995),(518,1976),(518,1976),(484,2010),(518,1976),(488,2006),(494,2000),(533,1961),(490,2004),(531,1963),(522,1972),(501,1993),(508,1986),(530,1964),(535,1959),(483,2011),(518,1976),(512,1982),(540,1954),(480,2014),(509,1985),(478,2016),(488,2006),(514,1980),(505,1989),(486,2008),(493,2001),(485,2009),(507,1987),(527,1967),(477,2017),(486,2008),(508,1986),(472,2022),(494,2000),(528,1966),(495,1999),(525,1969),(492,2002),(507,1987),(516,1978),(506,1988),(520,1974),(515,1979),(481,2013),(501,1993),(500,1994),(475,2019),(517,1977),(488,2006),(461,2033),(546,1948),(509,1985),(478,2016),(537,1957),(501,1993),(471,2023),(469,2025),(505,1989),(518,1976),(492,2002),(515,1979),(504,1990),(503,1991),(526,1968),(488,2006),(517,1977),(510,1984),(499,1995),(507,1987),(546,1948),(510,1984),(480,2014),(504,1990),(493,2001),(489,2005),(491,2003),(499,1995),(524,1970),(489,2005),(526,1968),(484,2010),(496,1998),(533,1961),(483,2011),(512,1982),(525,1969),(502,1992),(473,2021),(516,1978),(500,1994),(502,1992),(494,2000),(523,1971),(474,2020),(528,1966),(505,1989),(534,1960),(494,2000),(511,1983),(493,2001),(522,1972),(492,2002),(486,2008),(511,1983),(515,1979),(526,1968),(474,2020),(507,1987),(473,2021),(521,1973),(475,2019),(526,1968),(481,2013),(557,1937),(547,1947),(518,1976),(535,1959),(491,2003),(502,1992),(512,1982),(489,2005),(524,1970),(488,2006),(517,1977),(514,1980),(480,2014),(539,1955),(520,1974),(535,1959),(483,2011),(521,1973),(520,1974),(525,1969),(490,2004),(484,2010),(514,1979),(507,1986),(501,1992),(519,1974),(518,1975),(510,1983),(524,1969),(535,1958),(505,1988),(491,2002),(494,1999),(482,2011),(515,1978),(520,1973),(488,2005),(512,1981),(463,2030),(491,2002),(501,1992),(492,2001),(484,2009),(522,1971),(514,1979),(502,1991),(492,2001),(551,1942),(511,1982),(467,2026),(537,1956),(514,1979),(532,1961),(513,1980),(506,1987),(541,1952),(535,1958),(509,1984),(508,1985),(470,2023),(518,1975),(478,2015),(518,1975),(492,2001),(488,2005),(495,1998),(551,1942),(511,1982),(509,1984),(527,1966),(485,2008),(528,1965),(512,1981),(500,1993),(493,2000),(524,1969),(493,2000),(492,2001),(497,1996),(476,2017),(528,1965),(494,1999),(520,1973),(486,2007),(516,1977),(515,1978),(481,2012),(498,1995),(505,1988),(518,1975),(490,2003),(534,1959),(558,1935),(495,1998),(518,1975),(517,1976),(480,2013),(535,1958),(490,2003),(506,1987),(518,1975),(513,1980),(479,2014),(526,1967),(508,1985),(488,2005),(483,2010),(487,2006),(522,1971),(498,1995),(529,1964),(522,1971),(496,1997),(513,1980),(525,1968),(489,2004)]
TIMING: 4,888,128 ms

Realistic load, optimized cache miss cost (1ms)

The same as above, but a smaller cost for a cache miss.

benchmarking realistic requests x1000000, optimized 1ms miss cost/optimistic distribution/2xCPUs threads/unbounded
HITS/MISSES: [(105470,5642),(105511,5600),(105512,5599),(107414,3697),(107279,3832),(107355,3756),(107142,3969),(107090,4021),(107129,3982)]
TIMING:  13,057 ms

benchmarking realistic requests x1000000, optimized 1ms miss cost/optimistic distribution/2xCPUs threads/bounded effectively unbounded
HITS/MISSES: [(105470,5642),(105511,5600),(105512,5599),(107255,3856),(107263,3848),(107127,3984),(107359,3752),(107296,3815),(107089,4022)]
TIMING:  13,957 ms

benchmarking realistic requests x1000000, optimized 1ms miss cost/optimistic distribution/2xCPUs threads/bounded 10pct ideal capacity
HITS/MISSES: [(104957,6155),(104996,6115),(105011,6100),(105641,5470),(105522,5589),(105632,5479),(105640,5471),(105520,5591),(105562,5549)]
TIMING:  17,939 ms

benchmarking realistic requests x1000000, optimized 1ms miss cost/optimistic distribution/100xCPUs threads/unbounded
HITS/MISSES: [(2123,371),(2147,347),(2102,392),(2252,242),(2226,268),(2233,261),(2226,268),(2270,224),(2289,205),(2287,207),(2355,139),(2269,225),(2312,182),(2299,195),(2298,196),(2310,184),(2298,196),(2309,185),(2318,176),(2332,162),(2307,187),(2331,163),(2313,181),(2322,172),(2323,171),(2336,158),(2331,163),(2310,184),(2350,144),(2350,144),(2349,145),(2357,137),(2336,158),(2346,148),(2339,155),(2348,146),(2358,136),(2367,127),(2343,151),(2360,134),(2363,131),(2380,114),(2355,139),(2356,138),(2361,133),(2355,139),(2350,144),(2362,132),(2357,137),(2359,135),(2353,141),(2373,121),(2358,136),(2355,139),(2373,121),(2386,108),(2380,114),(2341,153),(2369,125),(2376,118),(2371,123),(2355,139),(2377,117),(2374,120),(2374,120),(2386,108),(2384,110),(2387,107),(2388,106),(2362,132),(2367,127),(2373,121),(2394,100),(2384,110),(2387,107),(2390,104),(2386,108),(2386,108),(2386,108),(2372,122),(2382,112),(2361,133),(2390,104),(2390,104),(2379,115),(2396,98),(2385,109),(2388,106),(2396,98),(2375,119),(2369,125),(2385,109),(2386,108),(2359,135),(2367,127),(2388,106),(2398,96),(2394,100),(2392,102),(2390,104),(2399,95),(2381,113),(2378,116),(2387,107),(2377,117),(2385,109),(2401,93),(2385,109),(2372,122),(2403,91),(2391,103),(2388,106),(2383,111),(2369,125),(2387,107),(2386,108),(2381,113),(2406,88),(2391,103),(2390,104),(2385,109),(2391,103),(2383,111),(2378,116),(2388,106),(2406,88),(2416,78),(2389,105),(2399,95),(2393,101),(2392,102),(2390,104),(2396,98),(2407,87),(2411,83),(2387,107),(2393,101),(2403,91),(2403,91),(2396,98),(2403,91),(2404,90),(2402,92),(2403,91),(2408,86),(2392,102),(2391,103),(2396,98),(2390,104),(2410,84),(2405,89),(2391,103),(2380,114),(2399,95),(2407,87),(2401,93),(2395,99),(2398,96),(2377,117),(2397,97),(2418,76),(2405,89),(2409,85),(2393,101),(2395,99),(2416,78),(2378,116),(2404,90),(2387,107),(2396,98),(2408,86),(2400,94),(2393,101),(2411,83),(2409,85),(2392,102),(2408,86),(2404,90),(2401,93),(2413,81),(2401,93),(2405,89),(2395,99),(2385,109),(2415,79),(2410,84),(2402,92),(2410,84),(2406,88),(2397,97),(2411,83),(2403,91),(2401,93),(2398,96),(2405,89),(2404,90),(2403,91),(2416,78),(2396,98),(2409,85),(2408,86),(2409,85),(2396,98),(2405,89),(2408,86),(2421,73),(2401,93),(2393,101),(2386,108),(2422,72),(2416,78),(2409,85),(2396,98),(2386,108),(2401,93),(2411,83),(2408,86),(2403,91),(2401,93),(2418,76),(2414,80),(2399,95),(2412,82),(2410,84),(2423,71),(2425,69),(2418,76),(2424,70),(2404,90),(2401,93),(2417,77),(2423,71),(2420,74),(2422,72),(2410,84),(2409,85),(2428,66),(2410,84),(2417,77),(2410,84),(2411,83),(2404,90),(2426,68),(2401,93),(2410,84),(2412,82),(2429,65),(2426,68),(2410,84),(2427,67),(2413,81),(2413,81),(2411,83),(2408,86),(2422,72),(2397,97),(2407,87),(2414,80),(2403,91),(2425,69),(2412,82),(2428,66),(2408,86),(2418,76),(2401,93),(2426,68),(2397,97),(2423,71),(2393,101),(2404,90),(2407,87),(2422,72),(2410,84),(2421,73),(2409,85),(2403,91),(2404,90),(2414,80),(2408,86),(2404,90),(2405,89),(2404,90),(2414,80),(2397,97),(2419,75),(2419,75),(2415,79),(2429,65),(2411,83),(2413,81),(2430,64),(2410,84),(2425,69),(2418,76),(2400,94),(2434,60),(2425,69),(2426,68),(2418,76),(2426,68),(2418,76),(2412,82),(2429,65),(2420,74),(2417,77),(2414,80),(2426,68),(2413,80),(2421,72),(2428,65),(2419,74),(2421,72),(2413,80),(2409,84),(2417,76),(2426,67),(2424,69),(2417,76),(2406,87),(2429,64),(2416,77),(2424,69),(2422,71),(2404,89),(2427,66),(2415,78),(2420,73),(2419,74),(2416,77),(2421,72),(2405,88),(2424,69),(2429,64),(2425,68),(2425,68),(2407,86),(2412,81),(2412,81),(2423,70),(2420,73),(2423,70),(2414,79),(2412,81),(2413,80),(2422,71),(2417,76),(2421,72),(2424,69),(2421,72),(2424,69),(2424,69),(2421,72),(2435,58),(2405,88),(2418,75),(2424,69),(2425,68),(2418,75),(2415,78),(2414,79),(2419,74),(2416,77),(2427,66),(2411,82),(2421,72),(2430,63),(2408,85),(2411,82),(2422,71),(2413,80),(2433,60),(2414,79),(2417,76),(2431,62),(2410,83),(2429,64),(2423,70),(2422,71),(2422,71),(2427,66),(2421,72),(2422,71),(2410,83),(2413,80),(2417,76),(2422,71),(2413,80),(2411,82),(2425,68),(2424,69),(2431,62),(2439,54),(2422,71),(2422,71),(2413,80),(2426,67),(2416,77),(2445,48),(2437,56),(2419,74),(2410,83)]
TIMING:  13,939 ms

benchmarking realistic requests x1000000, optimized 1ms miss cost/optimistic distribution/100xCPUs threads/bounded effectively unbounded
HITS/MISSES: [(2123,371),(2147,347),(2102,392),(2335,159),(2202,292),(2238,256),(2229,265),(2269,225),(2289,205),(2284,210),(2279,215),(2273,221),(2300,194),(2278,216),(2299,195),(2309,185),(2307,187),(2321,173),(2331,163),(2335,159),(2305,189),(2317,177),(2312,182),(2347,147),(2321,173),(2348,146),(2338,156),(2311,183),(2353,141),(2356,138),(2348,146),(2360,134),(2352,142),(2350,144),(2334,160),(2350,144),(2355,139),(2360,134),(2353,141),(2367,127),(2366,128),(2375,119),(2355,139),(2354,140),(2344,150),(2346,148),(2361,133),(2351,143),(2353,141),(2345,149),(2363,131),(2369,125),(2360,134),(2356,138),(2362,132),(2381,113),(2381,113),(2347,147),(2362,132),(2371,123),(2368,126),(2350,144),(2371,123),(2367,127),(2368,126),(2382,112),(2387,107),(2390,104),(2385,109),(2368,126),(2358,136),(2382,112),(2395,99),(2384,110),(2380,114),(2380,114),(2388,106),(2386,108),(2384,110),(2374,120),(2387,107),(2368,126),(2379,115),(2394,100),(2372,122),(2398,96),(2385,109),(2396,98),(2391,103),(2372,122),(2353,141),(2383,111),(2381,113),(2371,123),(2376,118),(2391,103),(2398,96),(2394,100),(2392,102),(2394,100),(2402,92),(2384,110),(2383,111),(2383,111),(2375,119),(2381,113),(2396,98),(2385,109),(2385,109),(2399,95),(2386,108),(2389,105),(2370,124),(2379,115),(2391,103),(2386,108),(2386,108),(2406,88),(2391,103),(2387,107),(2383,111),(2395,99),(2381,113),(2377,117),(2396,98),(2396,98),(2421,73),(2391,103),(2401,93),(2396,98),(2393,101),(2396,98),(2408,86),(2411,83),(2424,70),(2405,89),(2392,102),(2423,71),(2421,73),(2414,80),(2420,74),(2416,78),(2404,90),(2414,80),(2423,71),(2410,84),(2420,74),(2420,74),(2403,91),(2415,79),(2419,75),(2409,85),(2393,101),(2411,83),(2418,76),(2418,76),(2412,82),(2433,61),(2401,93),(2407,87),(2427,67),(2420,74),(2423,71),(2405,89),(2405,89),(2435,59),(2388,106),(2413,81),(2402,92),(2400,94),(2421,73),(2423,71),(2390,104),(2424,70),(2425,69),(2412,82),(2393,101),(2421,73),(2413,81),(2418,76),(2391,103),(2403,91),(2407,87),(2405,89),(2422,72),(2415,79),(2402,92),(2429,65),(2406,88),(2403,91),(2415,79),(2417,77),(2405,89),(2405,89),(2419,75),(2408,86),(2385,109),(2429,65),(2405,89),(2423,71),(2418,76),(2409,85),(2395,99),(2420,74),(2411,83),(2418,76),(2403,91),(2405,89),(2386,108),(2421,73),(2401,93),(2418,76),(2410,84),(2395,99),(2412,82),(2402,92),(2395,99),(2415,79),(2405,89),(2415,79),(2421,73),(2415,79),(2420,74),(2424,70),(2422,72),(2434,60),(2416,78),(2419,75),(2409,85),(2407,87),(2419,75),(2415,79),(2417,77),(2412,82),(2413,81),(2424,70),(2433,61),(2411,83),(2427,67),(2401,93),(2411,83),(2402,92),(2427,67),(2410,84),(2414,80),(2406,88),(2429,65),(2436,58),(2406,88),(2421,73),(2413,81),(2420,74),(2421,73),(2413,81),(2427,67),(2405,89),(2401,93),(2421,73),(2387,107),(2417,77),(2418,76),(2427,67),(2411,83),(2427,67),(2409,85),(2422,72),(2390,104),(2428,66),(2392,102),(2406,88),(2410,84),(2395,99),(2386,108),(2408,86),(2399,95),(2386,108),(2403,91),(2404,90),(2417,77),(2402,92),(2412,82),(2406,88),(2421,73),(2402,92),(2422,72),(2392,102),(2414,80),(2416,78),(2390,104),(2420,74),(2419,75),(2409,85),(2410,84),(2413,81),(2399,95),(2431,63),(2402,92),(2412,82),(2414,80),(2416,78),(2420,74),(2415,79),(2422,72),(2426,68),(2412,82),(2402,92),(2422,72),(2396,97),(2425,68),(2424,69),(2420,73),(2407,86),(2417,76),(2402,91),(2401,92),(2410,83),(2424,69),(2415,78),(2386,107),(2411,82),(2416,77),(2412,81),(2414,79),(2394,99),(2428,65),(2413,80),(2425,68),(2392,101),(2418,75),(2419,74),(2406,87),(2420,73),(2408,85),(2410,83),(2409,84),(2411,82),(2408,85),(2402,91),(2408,85),(2413,80),(2424,69),(2416,77),(2402,91),(2413,80),(2408,85),(2418,75),(2423,70),(2421,72),(2417,76),(2410,83),(2398,95),(2420,73),(2415,78),(2395,98),(2413,80),(2422,71),(2412,81),(2407,86),(2405,88),(2407,86),(2416,77),(2413,80),(2420,73),(2401,92),(2415,78),(2429,64),(2401,92),(2400,93),(2413,80),(2398,95),(2423,70),(2387,106),(2399,94),(2412,81),(2377,116),(2418,75),(2399,94),(2415,78),(2404,89),(2419,74),(2411,82),(2418,75),(2416,77),(2412,81),(2408,85),(2400,93),(2406,87),(2408,85),(2418,75),(2419,74),(2414,79),(2432,61),(2424,69),(2417,76),(2405,88),(2414,79),(2396,97),(2442,51),(2428,65),(2395,98),(2414,79)]
TIMING:  15,161 ms

benchmarking realistic requests x1000000, optimized 1ms miss cost/optimistic distribution/100xCPUs threads/bounded 10pct ideal capacity
HITS/MISSES: [(2123,371),(2147,347),(2106,388),(2286,208),(2221,273),(2226,268),(2217,277),(2242,252),(2272,222),(2291,203),(2285,209),(2303,191),(2303,191),(2290,204),(2317,177),(2309,185),(2302,192),(2309,185),(2327,167),(2341,153),(2313,181),(2326,168),(2322,172),(2345,149),(2320,174),(2357,137),(2346,148),(2309,185),(2355,139),(2340,154),(2345,149),(2350,144),(2346,148),(2363,131),(2350,144),(2339,155),(2362,132),(2367,127),(2337,157),(2365,129),(2353,141),(2369,125),(2344,150),(2358,136),(2354,140),(2358,136),(2354,140),(2359,135),(2357,137),(2356,138),(2358,136),(2374,120),(2361,133),(2350,144),(2369,125),(2379,115),(2379,115),(2348,146),(2369,125),(2377,117),(2371,123),(2359,135),(2378,116),(2373,121),(2360,134),(2386,108),(2378,116),(2394,100),(2380,114),(2360,134),(2361,133),(2372,122),(2396,98),(2387,107),(2384,110),(2361,133),(2382,112),(2376,118),(2377,117),(2363,131),(2382,112),(2362,132),(2376,118),(2388,106),(2364,130),(2392,102),(2373,121),(2379,115),(2377,117),(2374,120),(2358,136),(2377,117),(2378,116),(2351,143),(2359,135),(2385,109),(2389,105),(2377,117),(2380,114),(2371,123),(2385,109),(2373,121),(2360,134),(2372,122),(2368,126),(2365,129),(2373,121),(2390,104),(2359,135),(2389,105),(2372,122),(2369,125),(2360,134),(2360,134),(2381,113),(2378,116),(2362,132),(2395,99),(2366,128),(2376,118),(2356,138),(2371,123),(2374,120),(2358,136),(2363,131),(2382,112),(2403,91),(2369,125),(2373,121),(2377,117),(2369,125),(2375,119),(2373,121),(2382,112),(2383,111),(2369,125),(2368,126),(2373,121),(2370,124),(2366,128),(2368,126),(2373,121),(2372,122),(2369,125),(2388,106),(2374,120),(2373,121),(2385,109),(2362,132),(2377,117),(2378,116),(2358,136),(2354,140),(2366,128),(2383,111),(2383,111),(2365,129),(2367,127),(2343,151),(2376,118),(2376,118),(2373,121),(2377,117),(2380,114),(2348,146),(2394,100),(2356,138),(2391,103),(2365,129),(2359,135),(2387,107),(2378,116),(2360,134),(2377,117),(2377,117),(2360,134),(2372,122),(2368,126),(2378,116),(2372,122),(2370,124),(2380,114),(2365,129),(2364,130),(2392,102),(2377,117),(2375,119),(2387,107),(2373,121),(2371,123),(2374,120),(2370,124),(2369,125),(2372,122),(2372,122),(2378,116),(2361,133),(2390,104),(2363,131),(2395,99),(2369,125),(2374,120),(2367,127),(2363,131),(2371,123),(2391,103),(2375,119),(2362,132),(2353,141),(2387,107),(2376,118),(2376,118),(2363,131),(2352,142),(2368,126),(2364,130),(2363,131),(2372,122),(2368,126),(2385,109),(2377,117),(2361,133),(2381,113),(2369,125),(2378,116),(2384,110),(2392,102),(2376,118),(2368,126),(2376,118),(2378,116),(2379,115),(2379,115),(2372,122),(2367,127),(2369,125),(2388,106),(2374,120),(2384,110),(2365,129),(2383,111),(2359,135),(2382,112),(2369,125),(2376,118),(2368,126),(2388,106),(2384,110),(2370,124),(2383,111),(2374,120),(2387,107),(2387,107),(2362,132),(2389,105),(2366,128),(2353,141),(2384,110),(2362,132),(2381,113),(2367,127),(2389,105),(2372,122),(2375,119),(2366,128),(2384,110),(2350,144),(2376,118),(2359,135),(2375,119),(2368,126),(2371,123),(2365,129),(2386,108),(2364,130),(2336,158),(2366,128),(2363,131),(2369,125),(2358,136),(2365,129),(2370,124),(2390,104),(2354,140),(2372,122),(2377,117),(2373,121),(2381,113),(2369,125),(2381,113),(2396,98),(2374,120),(2382,112),(2378,116),(2378,116),(2391,103),(2383,111),(2377,117),(2369,125),(2375,119),(2382,112),(2374,120),(2383,111),(2386,108),(2378,116),(2372,122),(2390,104),(2363,130),(2384,109),(2384,109),(2382,111),(2373,120),(2364,129),(2361,132),(2368,125),(2382,111),(2388,105),(2369,124),(2364,129),(2377,116),(2370,123),(2378,115),(2384,109),(2347,146),(2390,103),(2368,125),(2386,107),(2374,119),(2389,104),(2383,110),(2361,132),(2371,122),(2384,109),(2387,106),(2381,112),(2370,123),(2371,122),(2352,141),(2377,116),(2373,120),(2370,123),(2367,126),(2374,119),(2361,132),(2359,134),(2381,112),(2380,113),(2384,109),(2378,115),(2388,105),(2363,130),(2389,104),(2392,101),(2354,139),(2380,113),(2381,112),(2383,110),(2379,114),(2370,123),(2367,126),(2382,111),(2375,118),(2372,121),(2375,118),(2365,128),(2392,101),(2359,134),(2351,142),(2369,124),(2363,130),(2395,98),(2348,145),(2377,116),(2380,113),(2357,136),(2385,108),(2377,116),(2375,118),(2373,120),(2373,120),(2366,127),(2376,117),(2370,123),(2350,143),(2369,124),(2376,117),(2365,128),(2366,127),(2361,132),(2378,115),(2386,107),(2379,114),(2374,119),(2382,111),(2375,118),(2363,130),(2356,137),(2403,90),(2388,105),(2366,127),(2370,123)]
TIMING:  18,900 ms

benchmarking realistic requests x1000000, optimized 1ms miss cost/realistic distribution/2xCPUs threads/unbounded
HITS/MISSES: [(29070,82042),(29031,82080),(29224,81887),(33332,77779),(34400,76711),(33945,77166),(33658,77453),(34091,77020),(33681,77430)]
TIMING: 228,574 ms

benchmarking realistic requests x1000000, optimized 1ms miss cost/realistic distribution/2xCPUs threads/bounded maxBound (10pct ideal capacity)
HITS/MISSES: [(29070,82042),(29031,82080),(29224,81887),(33342,77769),(34325,76786),(34077,77034),(33640,77471),(33204,77907),(34563,76548)]
TIMING: 231,087 ms

benchmarking realistic requests x1000000, optimized 1ms miss cost/realistic distribution/2xCPUs threads/bounded 6000 (1pct ideal capacity)
HITS/MISSES: [(22223,88889),(22087,89024),(22308,88803),(22395,88716),(22568,88543),(22142,88969),(22787,88324),(22358,88753),(22680,88431)]
TIMING: 262,072 ms

benchmarking realistic requests x1000000, optimized 1ms miss cost/realistic distribution/100xCPUs threads/unbounded
HITS/MISSES: [(303,2191),(303,2191),(306,2188),(630,1864),(426,2068),(476,2018),(497,1997),(497,1997),(489,2005),(471,2023),(467,2027),(473,2021),(477,2017),(539,1955),(548,1946),(594,1900),(605,1889),(585,1909),(605,1889),(586,1908),(612,1882),(596,1898),(589,1905),(534,1960),(556,1938),(538,1956),(557,1937),(577,1917),(586,1908),(567,1927),(552,1942),(556,1938),(558,1936),(548,1946),(583,1911),(525,1969),(630,1864),(577,1917),(612,1882),(660,1834),(622,1872),(622,1872),(637,1857),(604,1890),(618,1876),(610,1884),(640,1854),(594,1900),(629,1865),(632,1862),(618,1876),(592,1902),(587,1907),(623,1871),(612,1882),(671,1823),(637,1857),(667,1827),(683,1811),(723,1771),(646,1848),(640,1854),(620,1874),(625,1869),(639,1855),(622,1872),(669,1825),(696,1798),(626,1868),(677,1817),(651,1843),(682,1812),(638,1856),(772,1722),(672,1822),(712,1782),(682,1812),(641,1853),(649,1845),(660,1834),(700,1794),(694,1800),(697,1797),(717,1777),(705,1789),(684,1810),(700,1794),(675,1819),(671,1823),(688,1806),(703,1791),(679,1815),(694,1800),(697,1797),(688,1806),(703,1791),(649,1845),(657,1837),(753,1741),(718,1776),(700,1794),(688,1806),(702,1792),(716,1778),(706,1788),(653,1841),(693,1801),(678,1816),(704,1790),(676,1818),(649,1845),(686,1808),(721,1773),(719,1775),(685,1809),(680,1814),(692,1802),(701,1793),(742,1752),(703,1791),(681,1813),(671,1823),(700,1794),(691,1803),(689,1805),(687,1807),(692,1802),(721,1773),(744,1750),(745,1749),(718,1776),(723,1771),(728,1766),(707,1787),(702,1792),(773,1721),(706,1788),(730,1764),(741,1753),(719,1775),(731,1763),(735,1759),(734,1760),(700,1794),(735,1759),(743,1751),(690,1804),(689,1805),(705,1789),(714,1780),(747,1747),(731,1763),(729,1765),(750,1744),(702,1792),(713,1781),(716,1778),(755,1739),(701,1793),(769,1725),(745,1749),(769,1725),(761,1733),(745,1749),(706,1788),(728,1766),(725,1769),(758,1736),(768,1726),(781,1713),(785,1709),(701,1793),(709,1785),(729,1765),(710,1784),(718,1776),(738,1756),(774,1720),(763,1731),(727,1767),(714,1780),(727,1767),(740,1754),(741,1753),(716,1778),(722,1772),(712,1782),(731,1763),(726,1768),(712,1782),(751,1743),(702,1792),(756,1738),(734,1760),(733,1761),(693,1801),(745,1749),(765,1729),(760,1734),(725,1769),(742,1752),(779,1715),(741,1753),(741,1753),(692,1802),(721,1773),(749,1745),(736,1758),(793,1701),(763,1731),(765,1729),(747,1747),(709,1785),(756,1738),(735,1759),(751,1743),(779,1715),(742,1752),(806,1688),(828,1666),(727,1767),(750,1744),(804,1690),(791,1703),(717,1777),(726,1768),(732,1762),(703,1791),(732,1762),(800,1694),(724,1770),(756,1738),(769,1725),(716,1778),(802,1692),(713,1781),(750,1744),(788,1706),(790,1704),(778,1716),(729,1765),(767,1727),(794,1700),(780,1714),(815,1679),(767,1727),(732,1762),(788,1706),(777,1717),(797,1697),(778,1716),(760,1734),(763,1731),(756,1738),(734,1760),(743,1751),(769,1725),(725,1769),(760,1734),(809,1685),(772,1722),(747,1747),(790,1704),(745,1749),(793,1701),(766,1728),(793,1701),(752,1742),(786,1708),(776,1718),(782,1712),(783,1711),(806,1688),(778,1716),(778,1716),(796,1698),(778,1716),(783,1711),(758,1736),(765,1729),(755,1739),(762,1732),(816,1678),(752,1742),(788,1706),(818,1676),(753,1741),(764,1730),(822,1672),(807,1687),(772,1722),(779,1715),(800,1694),(744,1750),(820,1674),(763,1731),(822,1672),(809,1685),(798,1696),(809,1685),(784,1710),(812,1682),(780,1714),(790,1704),(816,1678),(821,1673),(823,1671),(755,1738),(781,1712),(773,1720),(782,1711),(785,1708),(742,1751),(798,1695),(776,1717),(807,1686),(756,1737),(768,1725),(772,1721),(785,1708),(811,1682),(796,1697),(778,1715),(804,1689),(826,1667),(791,1702),(796,1697),(765,1728),(771,1722),(806,1687),(793,1700),(789,1704),(812,1681),(754,1739),(770,1723),(763,1730),(801,1692),(804,1689),(774,1719),(772,1721),(803,1690),(798,1695),(801,1692),(799,1694),(816,1677),(784,1709),(824,1669),(778,1715),(850,1643),(826,1667),(785,1708),(774,1719),(781,1712),(805,1688),(771,1722),(805,1688),(856,1637),(788,1705),(809,1684),(810,1683),(824,1669),(777,1716),(763,1730),(795,1698),(788,1705),(824,1669),(805,1688),(807,1686),(829,1664),(796,1697),(776,1717),(813,1680),(750,1743),(803,1690),(789,1704),(789,1704),(798,1695),(816,1677),(770,1723),(769,1724),(817,1676),(839,1654),(805,1688),(820,1673),(817,1676),(800,1693),(835,1658),(817,1676),(791,1702),(795,1698),(817,1676),(818,1675),(809,1684),(744,1749),(853,1640),(785,1708),(798,1695),(836,1657),(765,1728),(798,1695),(777,1716)]
TIMING: 221,356 ms

benchmarking realistic requests x1000000, optimized 1ms miss cost/realistic distribution/100xCPUs threads/bounded maxBound (10pct ideal capacity)
HITS/MISSES: [(303,2191),(303,2191),(306,2188),(685,1809),(427,2067),(471,2023),(492,2002),(491,2003),(496,1998),(478,2016),(484,2010),(477,2017),(484,2010),(641,1853),(621,1873),(682,1812),(691,1803),(671,1823),(702,1792),(660,1834),(692,1802),(672,1822),(701,1793),(670,1824),(665,1829),(683,1811),(691,1803),(694,1800),(737,1757),(716,1778),(688,1806),(706,1788),(725,1769),(677,1817),(706,1788),(670,1824),(729,1765),(678,1816),(711,1783),(735,1759),(711,1783),(721,1773),(712,1782),(685,1809),(691,1803),(692,1802),(711,1783),(693,1801),(713,1781),(734,1760),(713,1781),(672,1822),(672,1822),(708,1786),(690,1804),(745,1749),(705,1789),(722,1772),(735,1759),(760,1734),(704,1790),(693,1801),(691,1803),(677,1817),(709,1785),(668,1826),(720,1774),(733,1761),(676,1818),(723,1771),(706,1788),(729,1765),(701,1793),(716,1778),(700,1794),(721,1773),(702,1792),(660,1834),(684,1810),(681,1813),(698,1796),(716,1778),(718,1776),(789,1705),(590,1904),(566,1928),(582,1912),(592,1902),(569,1925),(582,1912),(594,1900),(582,1912),(607,1887),(584,1910),(592,1902),(593,1901),(561,1933),(664,1830),(628,1866),(623,1871),(593,1901),(590,1904),(722,1772),(631,1863),(603,1891),(569,1925),(630,1864),(600,1894),(645,1849),(645,1849),(697,1797),(686,1808),(779,1715),(764,1730),(724,1770),(711,1783),(741,1753),(741,1753),(762,1732),(747,1747),(683,1811),(708,1786),(632,1862),(736,1758),(725,1769),(732,1762),(742,1752),(771,1723),(778,1716),(809,1685),(751,1743),(753,1741),(804,1690),(695,1799),(693,1801),(811,1683),(766,1728),(687,1807),(818,1676),(763,1731),(725,1769),(795,1699),(773,1721),(793,1701),(771,1723),(757,1737),(674,1820),(757,1737),(774,1720),(722,1772),(796,1698),(783,1711),(778,1716),(710,1784),(746,1748),(749,1745),(749,1745),(700,1794),(728,1766),(752,1742),(783,1711),(729,1765),(809,1685),(793,1701),(752,1742),(790,1704),(761,1733),(762,1732),(798,1696),(723,1771),(800,1694),(735,1759),(744,1750),(746,1748),(732,1762),(759,1735),(790,1704),(806,1688),(808,1686),(760,1734),(739,1755),(754,1740),(743,1751),(789,1705),(751,1743),(780,1714),(769,1725),(761,1733),(751,1743),(750,1744),(798,1696),(737,1757),(737,1757),(750,1744),(712,1782),(705,1789),(737,1757),(777,1717),(764,1730),(744,1750),(698,1796),(803,1691),(720,1774),(720,1774),(722,1772),(745,1749),(779,1715),(772,1722),(799,1695),(733,1761),(783,1711),(765,1729),(758,1736),(782,1712),(724,1770),(676,1818),(782,1712),(745,1749),(810,1684),(767,1727),(759,1735),(782,1712),(836,1658),(712,1782),(737,1757),(680,1814),(706,1788),(738,1756),(712,1782),(827,1667),(743,1751),(758,1736),(718,1776),(699,1795),(823,1671),(702,1792),(766,1728),(709,1785),(719,1775),(788,1706),(633,1861),(791,1703),(802,1692),(688,1806),(817,1677),(703,1791),(721,1773),(799,1695),(771,1723),(796,1698),(800,1694),(768,1726),(747,1747),(669,1825),(752,1742),(730,1764),(704,1790),(738,1756),(760,1734),(708,1786),(777,1717),(739,1755),(728,1766),(752,1742),(655,1839),(739,1755),(772,1722),(758,1736),(802,1692),(774,1720),(733,1761),(770,1724),(783,1711),(670,1824),(775,1719),(796,1698),(736,1758),(757,1737),(765,1729),(769,1725),(754,1740),(771,1723),(801,1693),(742,1752),(687,1807),(719,1775),(705,1789),(744,1750),(839,1655),(795,1699),(758,1736),(772,1722),(800,1694),(754,1740),(825,1669),(778,1716),(822,1672),(785,1709),(723,1771),(746,1748),(796,1698),(780,1714),(743,1751),(792,1702),(798,1696),(801,1693),(809,1685),(630,1863),(753,1740),(766,1727),(781,1712),(774,1719),(747,1746),(793,1700),(733,1760),(792,1701),(685,1808),(741,1752),(670,1823),(756,1737),(809,1684),(743,1750),(654,1839),(781,1712),(769,1724),(765,1728),(789,1704),(746,1747),(750,1743),(776,1717),(716,1777),(778,1715),(745,1748),(738,1755),(659,1834),(759,1734),(773,1720),(788,1705),(750,1743),(761,1732),(796,1697),(791,1702),(759,1734),(783,1710),(792,1701),(762,1731),(778,1715),(713,1780),(799,1694),(711,1782),(684,1809),(687,1806),(699,1794),(708,1785),(763,1730),(782,1711),(820,1673),(695,1798),(785,1708),(773,1720),(707,1786),(753,1740),(755,1738),(599,1894),(778,1715),(765,1728),(687,1806),(772,1721),(802,1691),(785,1708),(765,1728),(743,1750),(732,1761),(772,1721),(764,1729),(745,1748),(777,1716),(758,1735),(730,1763),(743,1750),(803,1690),(808,1685),(769,1724),(790,1703),(802,1691),(764,1729),(815,1678),(791,1702),(653,1840),(743,1750),(760,1733),(752,1741),(762,1731),(665,1828),(828,1665),(759,1734),(741,1752),(769,1724),(733,1760),(645,1848),(636,1857)]
TIMING: 225,848 ms

benchmarking realistic requests x1000000, optimized 1ms miss cost/realistic distribution/100xCPUs threads/bounded 6000 (1pct ideal capacity)
HITS/MISSES: [(303,2191),(303,2191),(306,2188),(476,2018),(467,2027),(476,2018),(436,2058),(479,2015),(479,2015),(453,2041),(453,2041),(482,2012),(481,2013),(436,2058),(475,2019),(504,1990),(525,1969),(492,2002),(510,1984),(493,2001),(509,1985),(525,1969),(509,1985),(479,2015),(519,1975),(506,1988),(505,1989),(505,1989),(535,1959),(517,1977),(517,1977),(491,2003),(522,1972),(492,2002),(525,1969),(484,2010),(519,1975),(479,2015),(504,1990),(539,1955),(496,1998),(497,1997),(516,1978),(509,1985),(516,1978),(491,2003),(519,1975),(488,2006),(514,1980),(518,1976),(508,1986),(480,2014),(468,2026),(512,1982),(510,1984),(531,1963),(493,2001),(531,1963),(530,1964),(572,1922),(510,1984),(523,1971),(486,2008),(479,2015),(523,1971),(480,2014),(511,1983),(539,1955),(487,2007),(541,1953),(522,1972),(519,1975),(497,1997),(523,1971),(497,1997),(517,1977),(520,1974),(489,2005),(494,2000),(489,2005),(519,1975),(529,1965),(505,1989),(517,1977),(528,1966),(498,1996),(521,1973),(522,1972),(488,2006),(496,1998),(511,1983),(494,2000),(511,1983),(474,2020),(506,1988),(518,1976),(473,2021),(485,2009),(535,1959),(510,1984),(499,1995),(498,1996),(489,2005),(536,1958),(508,1986),(469,2025),(526,1968),(494,2000),(544,1950),(504,1990),(468,2026),(514,1980),(530,1964),(561,1933),(520,1974),(501,1993),(492,2002),(492,2002),(519,1975),(521,1973),(508,1986),(483,2011),(493,2001),(501,1993),(508,1986),(512,1982),(503,1991),(494,2000),(526,1968),(511,1983),(500,1994),(526,1968),(525,1969),(511,1983),(509,1985),(529,1965),(489,2005),(505,1989),(526,1968),(503,1991),(515,1979),(504,1990),(518,1976),(485,2009),(503,1991),(513,1981),(498,1996),(510,1984),(506,1988),(498,1996),(526,1968),(499,1995),(497,1997),(518,1976),(484,2010),(502,1992),(495,1999),(534,1960),(476,2018),(543,1951),(519,1975),(531,1963),(551,1943),(500,1994),(498,1996),(495,1999),(526,1968),(540,1954),(549,1945),(508,1986),(537,1957),(469,2025),(477,2017),(502,1992),(489,2005),(490,2004),(499,1995),(531,1963),(526,1968),(494,2000),(484,2010),(512,1982),(490,2004),(506,1988),(486,2008),(473,2021),(479,2015),(505,1989),(491,2003),(501,1993),(496,1998),(478,2016),(475,2019),(505,1989),(521,1973),(473,2021),(510,1984),(500,1994),(511,1983),(468,2026),(483,2011),(543,1951),(503,1991),(498,1996),(446,2048),(500,1994),(491,2003),(504,1990),(523,1971),(523,1971),(483,2011),(489,2005),(480,2014),(524,1970),(491,2003),(508,1986),(509,1985),(514,1980),(535,1959),(526,1968),(496,1998),(493,2001),(543,1951),(508,1986),(461,2033),(473,2021),(483,2011),(479,2015),(498,1996),(542,1952),(497,1997),(495,1999),(510,1984),(455,2039),(564,1930),(471,2023),(512,1982),(536,1958),(513,1981),(510,1984),(481,2013),(473,2021),(516,1978),(518,1976),(532,1962),(483,2011),(493,2001),(506,1988),(503,1991),(558,1936),(535,1959),(497,1997),(515,1979),(496,1998),(489,2005),(485,2009),(513,1981),(470,2024),(499,1995),(540,1954),(496,1998),(468,2026),(512,1982),(473,2021),(513,1981),(497,1997),(530,1964),(521,1973),(530,1964),(494,2000),(505,1989),(503,1991),(521,1973),(497,1997),(503,1991),(525,1969),(511,1983),(505,1989),(480,2014),(513,1981),(496,1998),(499,1995),(538,1956),(479,2015),(499,1995),(505,1989),(484,2010),(479,2015),(543,1951),(549,1945),(523,1971),(506,1988),(523,1971),(473,2021),(552,1942),(502,1992),(539,1955),(517,1977),(494,2000),(527,1967),(506,1988),(525,1969),(491,2003),(508,1986),(531,1963),(518,1976),(504,1990),(494,1999),(465,2028),(494,1999),(511,1982),(512,1981),(481,2012),(517,1976),(494,1999),(526,1967),(477,2016),(488,2005),(519,1974),(510,1983),(531,1962),(512,1981),(504,1989),(510,1983),(551,1942),(500,1993),(537,1956),(499,1994),(498,1995),(493,2000),(506,1987),(505,1988),(528,1965),(500,1993),(479,2014),(466,2027),(504,1989),(532,1961),(463,2030),(481,2012),(499,1994),(514,1979),(536,1957),(502,1991),(494,1999),(502,1991),(514,1979),(505,1988),(530,1963),(516,1977),(467,2026),(482,2011),(501,1992),(488,2005),(486,2007),(528,1965),(544,1949),(492,2001),(508,1985),(501,1992),(512,1981),(484,2009),(484,2009),(459,2034),(476,2017),(508,1985),(505,1988),(489,2004),(494,1999),(506,1987),(489,2004),(501,1992),(468,2025),(503,1990),(499,1994),(496,1997),(517,1976),(497,1996),(491,2002),(481,2012),(506,1987),(520,1973),(478,2015),(530,1963),(530,1963),(512,1981),(534,1959),(531,1962),(515,1978),(470,2023),(503,1990),(512,1981),(477,2016),(476,2017),(537,1956),(483,2010),(483,2010),(523,1970),(466,2027),(507,1986),(471,2022)]
TIMING: 253,893 ms

Observations and TODOs

Observations:

  • Under the "realistic" assumption optimizing the cache miss path for plan
    generation might make an order of magnitude difference in throughput
  • The parameters of the distribution ("realistic distribution" vs "optimistic")
    make a huge difference in terms of the number of cache misses and
    consequently the throughput
  • Using an order of magnitude smaller bounded cache makes relatively little
    difference in terms of runtime (i.e. the benefit of the cache comes from
    caching the small number of very frequent elements). Compare the last three
    entries of Realistic load, with a realistic cost of a cache miss.

TODOs and action items (we can open issues for these, and edit them in here):

  • Update cache benchmarks so "realistic" benchmarks are synthetic #3551 The "realistic" benchmark results are decently approximated by just
    (total number of cache misses * miss cost) / capabilities. We should figure
    out the best way in criterion (or not) to just make these synthetic results
    to save a bunch of time.
  • Do a round of optimizations on plan generation #3550 It is worth at least an initial round of optimizing plan generation
  • Gather usage telemetry data for cache #3552 We should gather data about cache usage from users using telemetry:
    • count cache hits vs misses
    • periodically track cache size and perhaps an access histogram summary
      (what does the distribution look like?). This might depend on using a
      bounded cache (see below).
    • track request times for hit and miss paths separately; maybe just two microsecond Word counters that we always atomically add to
  • bound the size of query plan cache #5363 Consider making the bounded cache the default since...
    • it is equally effective for the use case that the cache was designed for: a finite number of elements
    • even a small size is similarly performant to unbounded when the domain is
      unbounded with long tail (note in this scenario the unbounded cache is
      inappropriate anyway since it implies unbounded space usage)
    • the bookkeeping in the LRU cache might allow us to collect important
      telemetry data from users (see above).
  • Once we gather more data: improve benchmarks to incorporate periodic scans, etc.
  • Experiment with other strategies (see comments to realisticBenches)

This was referenced Dec 17, 2019
Open
Open
Closed
@lexi-lambda lexi-lambda added the p/high candidate for being included in the upcoming sprint label Dec 17, 2019
jberryman added a commit to jberryman/graphql-engine that referenced this issue Dec 18, 2019
@jberryman
Initial benchmarks for caching. Closes hasura#3530
2fc7092 
These aren't suitable e.g. for running in CI since some take far too
long (and an impossibly long-time when running under criterion's normal
bootstrapping sampling regime.

We might try to improve this ourselves:
 haskell/criterion#218

An initial summary analysis will be in hasura#3530.
lexi-lambda added a commit that referenced this issue Dec 21, 2019
@lexi-lambda
Merge pull request #3534 from jberryman/internal-issue-317-understand…
b289148 
…-bounded-cache-performance

Understand bounded cache performance. Closes #3530
polRk pushed a commit to polRk/graphql-engine that referenced this issue Feb 12, 2020
@jberryman @polRk
Initial benchmarks for caching. Closes hasura#3530
e17cbc5 
These aren't suitable e.g. for running in CI since some take far too
long (and an impossibly long-time when running under criterion's normal
bootstrapping sampling regime.

We might try to improve this ourselves:
 haskell/criterion#218

An initial summary analysis will be in hasura#3530.
@tirumaraiselvan tirumaraiselvan mentioned this issue Jul 13, 2020
Closed
3 tasks
@sumodgeorge sumodgeorge mentioned this issue Nov 28, 2023
Open
@Allymahmoud Allymahmoud mentioned this issue Nov 28, 2023
Open
@ptakpatryk ptakpatryk mentioned this issue Dec 19, 2023
Open
This was referenced Apr 6, 2024
Open
Open
This was referenced Apr 6, 2024
Open
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@jberryman jberryman

Labels
c/server Related to server p/high candidate for being included in the upcoming sprint
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@jberryman @lexi-lambda @tirumaraiselvan