Monday, October 5, 2009

Wait-Free Cache Allocator, Part 3!

Yeah, it's been a while since I posted on this so I wanted to give a quick status on how it's working out...

There are four different types of tests:
  • Raw (r): Simple new/delete allocation scheme where each request for memory causes an allocation.
  • Blocked (b): Allocates in blocks handing out a chunk at a time. Enforces thread safety using mutexes.
  • Unblocked (ub): Just like unblocked except it is totally NOT thread safe...
  • Atomic (a): The pseudo-wait-free allocator I've been working on. (it's not actually wait free... to make it truly wait free would probably make it less efficient and take too long.)

The raw allocator is my baseline for the tests but I try to compare all of the results against each other. I'm still working on the test framework, but here are the results from a single thread running all four tests at various iterations, all of which allocate in bulk, then deallocate randomly. Yes, yes, I know, what's the point in a single threaded test of something that's multithreaded... it's just a baseline to see how it performs in non-threaded situations (where it SHOULDN'T be used, but still...)

ANYWAYS, here's the results:

000: Iters[    382]: r[ 0.0002822] b[ 0.0003256] ub[ 0.0001308] a[ 0.0001301]
001: Iters[ 573]: r[ 0.0003111] b[ 0.0004795] ub[ 0.0001159] a[ 0.0001418]
002: Iters[ 859]: r[ 0.0004065] b[ 0.0005000] ub[ 0.0001171] a[ 0.0001703]
003: Iters[ 1288]: r[ 0.0005679] b[ 0.0007953] ub[ 0.0001349] a[ 0.0004345]
004: Iters[ 1932]: r[ 0.0007991] b[ 0.0010567] ub[ 0.0001510] a[ 0.0002469]
005: Iters[ 2898]: r[ 0.0011374] b[ 0.0014791] ub[ 0.0002087] a[ 0.0003129]
006: Iters[ 4347]: r[ 0.0016636] b[ 0.0022002] ub[ 0.0001988] a[ 0.0004183]
007: Iters[ 6520]: r[ 0.0024785] b[ 0.0040991] ub[ 0.0002672] a[ 0.0005800]
008: Iters[ 9780]: r[ 0.0035872] b[ 0.0047101] ub[ 0.0003520] a[ 0.0008599]
009: Iters[ 14670]: r[ 0.0053226] b[ 0.0074197] ub[ 0.0004619] a[ 0.0011902]
010: Iters[ 22005]: r[ 0.0080567] b[ 0.0107315] ub[ 0.0008942] a[ 0.0019779]
011: Iters[ 33007]: r[ 0.0122470] b[ 0.0168040] ub[ 0.0011022] a[ 0.0027471]
012: Iters[ 49510]: r[ 0.0179474] b[ 0.0267609] ub[ 0.0018665] a[ 0.0045312]
013: Iters[ 74265]: r[ 0.0275046] b[ 0.0363858] ub[ 0.0027583] a[ 0.0066835]
014: Iters[ 111397]: r[ 0.0411089] b[ 0.0552259] ub[ 0.0036272] a[ 0.0094744]
015: Iters[ 167095]: r[ 0.0611580] b[ 0.0819954] ub[ 0.0060764] a[ 0.0145781]
016: Iters[ 250642]: r[ 0.0958014] b[ 0.1236177] ub[ 0.0086538] a[ 0.0212276]
017: Iters[ 375963]: r[ 0.1448224] b[ 0.1847220] ub[ 0.0142410] a[ 0.0322124]
018: Iters[ 563944]: r[ 0.2254061] b[ 0.3297470] ub[ 0.0198752] a[ 0.0479318]
019: Iters[ 845916]: r[ 0.3327258] b[ 0.4203867] ub[ 0.0283150] a[ 0.0709337]
TimePer: raw[0.000388] blocked[0.000516] unblocked[0.000035] atomic[0.000085]
Percent of raw: blocked[1.331635] unblocked[0.091066] atomic[0.220457]
Average: raw[0.098333] blocked[0.130944] unblocked[0.008955] atomic[0.021678]