>Why don't you just use that data of the width specification from the >LC_CTYPE of the current locale? That is probably much faster to get >access to, it is just one indexing operation instead of a number of if's. >And you get free upgrade when the locale is upgraded. first off LC_CTYPE is an outdated concept, and should be dispensed with. (the width function im thinking of expects utf-8, and the system wcwidth expects ucs-4, locale regardless ) Locales should really be about how you want to see dates/times formatted, and which string constants you want apps to spit out in error messages and the like. They should desist supporting outmoded encodings. (iso-8859-*,euc-*,*jis*,tcvn&friends) secondly, having a 2 megabyte array around just for looking up widths can be faster, assuming you have a really good virtual memory system, and gobs of ram. However, i still think a tree is the correct compromise. >They're both O(log n) compares. They're doing the same thing, except >a binary tree conceptually moves the binary search logic into the data >structure. i was imagining perhaps the difference between O(2 log n) and O(log n) would still be worthwhile :) >It's the complexity of the whole that I'm referring to, and setting up a >tree is much more complicated. (You actually suggested code generation, >which is orders of magnitude more complex.) well, I wouldnt want to let the difficulty of statically initializing data structures in c determine my algorithms. ill come up with an implementation + benchmark, for fun if nothing else. ok, done: if anyone is interested there should be a tarball attached which implements the tree thing, and benchmarks it. on my system, its ~70% faster for widthing the whole unicode. caveat: range.dat isnt complete: id have to comb through 0x500-0x1100 range to get accurate accounting for single width/invalid char distinctions. (mk_wcwidth also glosses over distinctions in that range; many glyphs it reports as width 1 are in fact undefined) this technique could also be usefull for making language-membership decision trees. >I wrote the code first of all to specify the semantics of the function, >even though I don't think it does anything tremendously inefficent, and >I have not yet received a single profiling report that suggests that any >CPU on this planet spends a percentage of its time in this function that >would make it worthwhile to think about a serious optimization research >project. youre right, the difference is likely insignificant upwards of 99% of the time. (for me the difference was 0.130 seconds for widthing all 0 to 2^21) you'd have to be typesetting megs of data onto a char-cell output (perhaps a gigantic man-page) for it to matter
Attachment:
wbt.tar.gz
Description: GNU Zip compressed data