[add 'best' caching to page lists, helping with fragmentation issues
John Meacham <john@repetae.net>**20100407060201
 Ignore-this: 8c444ed01cc90b92edb44f004700cc5b
] hunk ./src/data/rts/slub.c 77
-static unsigned page_threshold = 4;
+static unsigned page_threshold = 8;
hunk ./src/data/rts/slub.c 105
+
+                // 'best' keeps track of the page with the fewest free spots
+                // and percolates it to the front, effectively a single pass
+                // of a bubblesort to help combat fragmentation. It does
+                // not increase the complexity of the cleanup algorithm as
+                // we had to scan every page anyway, but over many passes
+                // of the GC it will eventually result in a more sorted list
+                // than would occur by chance.
+
+                struct s_page *best = NULL;
+                int free_best = 4096;
hunk ./src/data/rts/slub.c 132
-                                SLIST_INSERT_HEAD(&sc->pages,pg,link);
+                                if(!best) {
+                                        free_best = pg->num_free;
+                                        best = pg;
+                                } else {
+                                        if(pg->num_free < free_best) {
+                                                struct s_page *tmp = best;
+                                                best = pg;
+                                                pg = tmp;
+                                                free_best = pg->num_free;
+                                        }
+                                        SLIST_INSERT_HEAD(&sc->pages,pg,link);
+                                }
hunk ./src/data/rts/slub.c 145
-
hunk ./src/data/rts/slub.c 151
+                if(best)
+                        SLIST_INSERT_HEAD(&sc->pages,best,link);