On Wed, Nov 12, 2008 at 19:05, Alan Jenkins <alan-jenkins@xxxxxxxxxxxxxx> wrote: > Kay Sievers wrote: >> On Wed, Nov 12, 2008 at 17:50, Alan Jenkins <alan-jenkins@xxxxxxxxxxxxxx> wrote: >>> Kay Sievers wrote: >>>> On Tue, Nov 11, 2008 at 22:23, Kay Sievers <kay.sievers@xxxxxxxx> wrote: >>>>> On Tue, Nov 11, 2008 at 21:20, Alan Jenkins <alan-jenkins@xxxxxxxxxxxxxx> wrote: >>>>> >>>>>> On my Ubuntu installation this removes 15k of duplicate strings, >>>>>> using a temporary index of about 25k. >>>>>> >>>>> Great. That looks nice. >>>>> >>>>> Thats's the diff of the rule dump before and after the patch: >>>>> ... >>>>> -[] shrunk to 64896 bytes tokens (5408 * 12 bytes), 57298 bytes buffer >>>>> -[] dumping 5408 (64896 bytes) tokens, 5818 (57298 bytes) strings >>>>> +[] shrunk to 64896 bytes tokens (5408 * 12 bytes), 18204 bytes buffer >>>>> +[] used 40512 bytes of string index nodes (844 * 48 bytes) >>>>> +[] dumping 5408 (64896 bytes) tokens, 1369 (18204 bytes) strings >>>>> >>>> I split the nodes and the childs in two independent arrays, so we got >>>> rid of the limit of 10 childs per node. I've got ~200 fully uses slots >>>> with the huge rules set here. Unlimited childs in the index removes >>>> another 3 kB of duplicates, and the temporary index seems also a bit >>>> smaller: >>>> shrunk to 64896 bytes tokens (5408 * 12 bytes), 15324 bytes buffer >>>> used 29456 bytes for index (1076 * 16 bytes nodes, 1020 * 12 bytes >>>> child links) >>>> >>>> Would be great, if you can check if it still works for you as expected. :) >>>> >>> Did you have a particular reason to keep the trie_root array? Now >>> there's no fixed limit on children, you could just use trie[1] as the >>> root node. Remove the special case for depth == 0. And initialize it's >>> value and length to 0, then you can remove the special case for len == 0. >>> >> >> No special reason, I thought about that too, but it was already 5am, >> and I was unable to think it through. :) >> >> Sounds nice to do that, did you try already, have a patch? >> > No, sorry :). Ah, now by looking at it, maybe the then needed linear search for the key in the root is not as good as the plain root array index? Kay -- To unsubscribe from this list: send the line "unsubscribe linux-hotplug" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
