<div dir="ltr">You're 4.5 hours too late, I'm afraid. I'd be happy to take some patches though. :-) </div><div class="gmail_extra"> <div class="gmail_quote">On Wed, Mar 7, 2018 at 4:42 PM, Dylan Baker <<a href="mailto:dylan@pnwbakers.com" target="_blank">dylan@pnwbakers.com</a>> wrote: <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Quoting Jason Ekstrand (2018-03-07 06:34:52) <div><div class="h5">> The original string map assumed that the mapping from strings to > entrypoints was a bijection. This will not be true the moment we > add entrypoint aliasing. This reworks things to be an arbitrary map > from strings to non-negative signed integers. The old one also had a > potential bug if we ever had a hash collision because it didn't do the > strcmp inside the lookup loop. While we're at it, we break things out > into a helpful class. > > Reviewed-by: Lionel Landwerlin <<a href="mailto:lionel.g.landwerlin@intel.com">lionel.g.landwerlin@intel.com</a>> > Reviewed-by: Samuel Iglesias Gonsálvez <<a href="mailto:siglesias@igalia.com">siglesias@igalia.com</a>> > --- > src/intel/vulkan/anv_entrypoints_gen.py | 188 +++++++++++++++++--------------- > 1 file changed, 103 insertions(+), 85 deletions(-) > > diff --git a/src/intel/vulkan/anv_entrypoints_gen.py b/src/intel/vulkan/anv_entrypoints_gen.py > index 34ffedb..dc0f0e9 100644 > --- a/src/intel/vulkan/anv_entrypoints_gen.py > +++ b/src/intel/vulkan/anv_entrypoints_gen.py > @@ -115,9 +115,10 @@ TEMPLATE_C = Template(u"""\ > > #include "anv_private.h" > > -struct anv_entrypoint { > +struct string_map_entry { > uint32_t name; > uint32_t hash; > + uint32_t num; > }; > > /* We use a big string constant to avoid lots of reloctions from the entry > @@ -126,17 +127,60 @@ struct anv_entrypoint { > */ > > static const char strings[] = > -% for e in entrypoints: > - "${<a href="http://e.name" rel="noreferrer" target="_blank">e.name</a>}\\0" > +% for s in strmap.sorted_strings: > + "${s.string}\\0" > % endfor > ; > > -static const struct anv_entrypoint entrypoints[] = { > -% for e in entrypoints: > - [${e.num}] = { ${offsets[e.num]}, ${'{:0=#8x}'.format(e.get_c_hash())} }, /* ${<a href="http://e.name" rel="noreferrer" target="_blank">e.name</a>} */ > +static const struct string_map_entry string_map_entries[] = { > +% for s in strmap.sorted_strings: > + { ${s.offset}, ${'{:0=#8x}'.format(s.hash)}, ${s.num} }, /* ${s.string} */ > % endfor > }; > > +/* Hash table stats: > + * size ${len(strmap.sorted_strings)} entries > + * collisions entries: > +% for i in xrange(10): > + * ${i}${'+' if i == 9 else ' '} ${strmap.collisions[i]} > +% endfor > + */ > + > +#define none 0xffff > +static const uint16_t string_map[${strmap.hash_size}] = { > +% for e in strmap.mapping: > + ${ '{:0=#6x}'.format(e) if e >= 0 else 'none' }, > +% endfor > +}; > + > +static int > +string_map_lookup(const char *str) > +{ > + static const uint32_t prime_factor = ${strmap.prime_factor}; > + static const uint32_t prime_step = ${strmap.prime_step}; > + const struct string_map_entry *e; > + uint32_t hash, h; > + uint16_t i; > + const char *p; > + > + hash = 0; > + for (p = str; *p; p++) > + hash = hash * prime_factor + *p; > + > + h = hash; > + while (1) { > + i = string_map[h & ${strmap.hash_mask}]; > + if (i == none) > + return -1; > + e = &string_map_entries[i]; > + if (e->hash == hash && strcmp(str, strings + e->name) == 0) > + return e->num; > + h += prime_step; > + } > + > + return -1; > +} > + > /* Weak aliases for all potential implementations. These will resolve to > * NULL if they're not defined, which lets the resolve_entrypoint() function > * either pick the correct entry point. > @@ -275,54 +319,10 @@ anv_resolve_entrypoint(const struct gen_device_info *devinfo, uint32_t index) > return anv_dispatch_table.entrypoints[index]; > } > > -/* Hash table stats: > - * size ${hash_size} entries > - * collisions entries: > -% for i in xrange(10): > - * ${i}${'+' if i == 9 else ''} ${collisions[i]} > -% endfor > - */ > - > -#define none ${'{:#x}'.format(none)} > -static const uint16_t map[] = { > -% for i in xrange(0, hash_size, 8): > - % for j in xrange(i, i + 8): > - ## This is 6 because the 0x is counted in the length > - % if mapping[j] & 0xffff == 0xffff: > - none, > - % else: > - ${'{:0=#6x}'.format(mapping[j] & 0xffff)}, > - % endif > - % endfor > -% endfor > -}; > - > int > anv_get_entrypoint_index(const char *name) > { > - static const uint32_t prime_factor = ${prime_factor}; > - static const uint32_t prime_step = ${prime_step}; > - const struct anv_entrypoint *e; > - uint32_t hash, h, i; > - const char *p; > - > - hash = 0; > - for (p = name; *p; p++) > - hash = hash * prime_factor + *p; > - > - h = hash; > - do { > - i = map[h & ${hash_mask}]; > - if (i == none) > - return -1; > - e = &entrypoints[i]; > - h += prime_step; > - } while (e->hash != hash); > - > - if (strcmp(name, strings + e->name) != 0) > - return -1; > - > - return i; > + return string_map_lookup(name); > } > > void * > @@ -334,7 +334,6 @@ anv_lookup_entrypoint(const struct gen_device_info *devinfo, const char *name) > return anv_resolve_entrypoint(devinfo, idx); > }""", output_encoding='utf-8') > > -NONE = 0xffff > HASH_SIZE = 256 > U32_MASK = 2**32 - 1 > HASH_MASK = HASH_SIZE - 1 > @@ -342,11 +341,54 @@ HASH_MASK = HASH_SIZE - 1 > PRIME_FACTOR = 5024183 > PRIME_STEP = 19 > > - > -def cal_hash(name): > - """Calculate the same hash value that Mesa will calculate in C.""" > - return functools.reduce( > - lambda h, c: (h * PRIME_FACTOR + ord(c)) & U32_MASK, name, 0) > +class StringIntMapEntry(object): > + def __init__(self, string, num): > + self.string = string > + self.num = num > + > + # Calculate the same hash value that we will calculate in C. > + h = 0 > + for c in string: > + h = ((h * PRIME_FACTOR) + ord(c)) & U32_MASK > + self.hash = h </div></div>why no love for my use of reduce? > + > + self.offset = None > + This needs a __hash__ method, def __hash__(self): return self.hash is probably sufficient > +class StringIntMap(object): > + def __init__(self): > + self.baked = False > + self.strings = dict() can we add all of the instance attributes in the constructor please? just set them to None or something? > + > + def add_string(self, string, num): > + assert not self.baked > + assert string not in self.strings > + assert num >= 0 and num < 2**31 > + self.strings[string] = StringIntMapEntry(string, num) > + > + def bake(self): > + self.sorted_strings = \ > + sorted(self.strings.values(), key=lambda x: x.string) > + offset = 0 > + for entry in self.sorted_strings: > + entry.offset = offset > + offset += len(entry.string) + 1 how about: self.offset = sum(len(e.string) + 1 for e in self.sorted_strings) <div><div class="h5"> > + > + # Save off some values that we'll need in C > + self.hash_size = HASH_SIZE > + self.hash_mask = HASH_SIZE - 1 > + self.prime_factor = PRIME_FACTOR > + self.prime_step = PRIME_STEP > + > + self.mapping = [-1] * self.hash_size > + self.collisions = [0] * 10 > + for idx, s in enumerate(self.sorted_strings): > + level = 0 > + h = s.hash > + while self.mapping[h & self.hash_mask] >= 0: > + h = h + PRIME_STEP > + level = level + 1 > + self.collisions[min(level, 9)] += 1 > + self.mapping[h & self.hash_mask] = idx > > EntrypointParam = namedtuple('EntrypointParam', 'type name decl') > > @@ -372,9 +414,6 @@ class Entrypoint(object): > def call_params(self): > return ', '.join(<a href="http://p.name" rel="noreferrer" target="_blank">p.name</a> for p in self.params) > > - def get_c_hash(self): > - return cal_hash(<a href="http://self.name" rel="noreferrer" target="_blank">self.name</a>) > - > def get_entrypoints(doc, entrypoints_to_defines, start_index): > """Extract the entry points from the registry.""" > entrypoints = OrderedDict() > @@ -443,36 +482,15 @@ def get_entrypoints_defines(doc): > > def gen_code(entrypoints): > """Generate the C code.""" > - i = 0 > - offsets = [] > - for e in entrypoints: > - offsets.append(i) > - i += len(<a href="http://e.name" rel="noreferrer" target="_blank">e.name</a>) + 1 > > - mapping = [NONE] * HASH_SIZE > - collisions = [0] * 10 > + strmap = StringIntMap() > for e in entrypoints: > - level = 0 > - h = e.get_c_hash() > - while mapping[h & HASH_MASK] != NONE: > - h = h + PRIME_STEP > - level = level + 1 > - if level > 9: > - collisions[9] += 1 > - else: > - collisions[level] += 1 > - mapping[h & HASH_MASK] = e.num > + strmap.add_string(<a href="http://e.name" rel="noreferrer" target="_blank">e.name</a>, e.num) > + strmap.bake() > > return TEMPLATE_C.render(entrypoints=entrypoints, > LAYERS=LAYERS, > - offsets=offsets, > - collisions=collisions, > - mapping=mapping, > - hash_mask=HASH_MASK, > - prime_step=PRIME_STEP, > - prime_factor=PRIME_FACTOR, > - none=NONE, > - hash_size=HASH_SIZE, > + strmap=strmap, > filename=os.path.basename(__file__)) > > > -- > 2.5.0.400.gff86faf > </div></div>> _______________________________________________ > mesa-dev mailing list > <a href="mailto:mesa-dev@lists.freedesktop.org">mesa-dev@lists.freedesktop.org</a> > <a href="https://lists.freedesktop.org/mailman/listinfo/mesa-dev" rel="noreferrer" target="_blank">https://lists.freedesktop.org/mailman/listinfo/mesa-dev</a> </blockquote></div> </div>