Kay Sievers wrote: > On Wed, 2008-11-12 at 20:48 +0000, Alan Jenkins wrote: > >> Kay Sievers wrote: >> >>> 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? >>> >>> >> Mmm. Ok, without the root array add_string() takes twice as long, which >> increases the total rules-loading time by 10%. (user time measured by >> cachegrind). Let's leave it. >> > > Hmm, now I liked the idea. :) > > How about this? It has only a single array again, and no root, and no > child limits. Seems to work fine, but, it looks somehow too simple > now. :) > Simple is good. It's no faster, but I shouldn't care about 10% load time - because the total is only 0.01 seconds. What matters is that you can understand it, and rewriting it yourself won't hurt :). As I say, the len==0 special case is now redundant. If you remove it, it'll get handled by the root node which represents the empty string. > @@ -460,37 +456,31 @@ static int add_string(struct udev_rules *rules, const char *str) > if (len == 0) > return 0; Thanks Alan -- 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
