Ok. The new voxel rendering algorithm performs 1.4 times faster. Not much, but voxel models can also be split into 16-bit chunks, which locally use only 16-bit addressing. That should speedup the algorithm further, if the bottleneck is with the memory bandwidth.
I've also discovered that GCC's __builtin_popcount is slower than a lookup table, since it branches into subroutine __popcountdi2. Why GCC doesnt use the x86 popcnt opcode? No idea. No idea. But it probably would be easier to answer why Stallman molests little children.
For a long time I have been using a hashtable library made by other people. It had its drawbacks. In particular I have to acknowledge the original authors in the credits of my software, and its hash function is far from being perfect.
For example, here is their hash Bernstein function applied to the various modifications of the string "hello": 0f8fff15: hallo 0f908b76: hbllo 0f9117d7: hcllo 0f91a438: hdllo 0f923099: hello 0f92bcfa: hfllo 0f93495b: hgllo 0f93d5bc: hhllo 0f94621d: hillo 0f94ee7e: hjllo 0f957adf: hkllo 0f960740: hlllo 0f9693a1: hmllo 0f972002: hnllo 0f97ac63: hollo 0f9838c4: hpllo 0f98c525: hqllo 0f995186: hrllo 0f99dde7: hsllo 0f9a6a48: htllo 0f9af6a9: hullo 0f9b830a: hvllo 0f9c0f6b: hwllo 0f9c9bcc: hxllo 0f9d27ee: hyll0 0f9d27ef: hyll1 0f9d27f0: hyll2 0f9d27f1: hyll3 0f9d27f2: hyll4 0f9d27f3: hyll5 0f9d27f4: hyll6 0f9d27f5: hyll7 0f9d27f6: hyll8 0f9d282d: hyllo
Obviously the hash code is patterned and these paterns depend heavily on the input string. That is important since in real life we almost always have a house addresses differing in just a single letter or program identifiers, like var1, var2, var3, so such hash wont work with real world data. There is also this Jenkins hash, it is far better and works with real life data, but a bit more expensive and still has patterns recognizable by naked eye without any statistical analyzis. So I have devised my own hash function based on several 8-bit tables. It can be further improved indefinitely by adding more tables:
>>43 Why did you test your hash function on input that differs on multiple bytes, but djb's on only one? Is this because you didn't benchmark hashtable performance between the two, and your hash function remains but unproven wibble? (we've all been there.)
Name:
Anonymous2020-10-06 12:50
>>44 No it were Wesnoth team, who stole music from Krondor. I've used creative commons music in the prototype.
Name:
Anonymous2020-10-06 12:55
>>46 What? I've applied both to the same "hello" set word with a few letters changed to demonstrate the shortcomings of simpler hash functions. I've just sorted both outputs to show how the first digits are always the same in djb case, but properly distributed in my personal hash function.
Here is the code char hell[] = "hello"; for (int i = 'a'; i < 'z'; i++) { hell[1] = i; printf("%08x: %s\n", hash_cstr(hell), hell); } for (int i = '0'; i < '9'; i++) { hell[4] = i; printf("%08x: %s\n", hash_cstr(hell), hell); }
which was ran as ./a.out | sort
So yeah, even hashing a "hello" properly can lead to issues.
Although mine uses several tables - one for each input byte, and doesn't use the hash value itself for lookup since that can reduce the speed a bit. And it also generates only the required number of bits for the power of two hash table, so I don't have to do hascode&table_size
Note how methods can be called on both pointers and direct values. I.e. this.push(123) would be totally fine.
Name:
Anonymous2020-10-12 21:30
>>52 And the code rewriting this shit is not he most beautiful code around: sym_t *pg_declof2(cnode_t *n) { if (!n) return 0; if (n->id == N_BLOCK) { //for GCC block expressions return 0; } else if (n->id == (IDENTIFIER|N_TERM)) { sym_t *s = lookup(n->text); if (s) { return s; } else { return 0; } } else if (n->id == N_EXPR) { return 0; } else if (n->id == N_BEXPR) { for (; n && n->id==N_BEXPR ; n = n->tail) { sym_t *decl = pg_declof2(n->head); if (decl) return decl; } if (n) { return pg_declof2(n); } return 0; } else if (n->id == N_DECL) { return 0; } else if (n->id == N_UNARY) { char c = n->head->text[0]; if (c == '*') pg_declof_ptr_lv--; else if (c == '&') pg_declof_ptr_lv++; return pg_declof2(n->tail); } else if (n->id == N_INDEX) { pg_declof_ptr_lv--; return pg_declof2(n->head); } else if (n->id & N_TERM) { return 0; } else if (n->id == N_LIT) { return 0; } else if (n->id == N_DOT || n->id == N_ARROW) { sym_t *l = pg_declof2(n->head); if (!l) return 0; char *name = n->tail->text; char *tname = pg_typename(l->type); char *mname; sym_t *s; int plv = ptr_level(l->decl); if ((n->id == N_DOT && plv != 1) || (n->id == N_ARROW && plv == 1)) { mname = sjoin3(tname, "_mf_", name); //field accessor s = lookup(mname); free(mname); if (s) return s; return 0; } mname = sjoin3(tname, "_m_", name); s = lookup(mname); free(mname); if (s) return s; return 0; } else if (n->id == N_CALL) { if (n->head->id != N_DOT) return pg_declof2(n->head); n = n->head; sym_t *l = pg_declof2(n->head); if (!l) return 0; pg_declof_ptr_lv += ptr_level(l->decl); char *name = n->tail->text; char *tname = pg_typename(l->type); char *mname; sym_t *s; mname = sjoin3(tname, "_m_", name); s = lookup(mname); free(mname); if (s) return s; return 0; } return 0; }
Name:
Anonymous2020-10-12 22:40
Implemented auto keyword. Which make declaration type be the type of its initializer.
Here is the code handling auto vars: static void pg_decl(cnode_t *n) { cnode_t *type = n->head; cnode_t *vars = n->tail; cnode_t *s = is_struct(type); if (s) { pg_struct(s, type, vars); } else { indent(); log("vars:\n"); if (type->id==N_TYPE_STOR && type->head->id == (AUTO|N_TERM)) { cnode_t *expr = vars->head->tail; sym_t *s = pg_declof(expr); if (!s) goto normal; int ptrc = ptr_level(s->decl)+pg_declof_ptr_lv; if (ptrc < 0) ptrc = 0; char *tname = pg_typename(s->type); char *ps = malloc(ptrc+1); for (int i = 0; i < ptrc; i++) ps[i] = '*'; ps[ptrc] = 0; char *ts = sjoin(tname,ps); free(ps); patch_t *p = new_patch(P_AUTO, n->sofs); p->as[0].s = ts; p->as[1].i = type->eofs; type = s->type; return; } normal: pg_vars(type, vars); } }
It doesn't allow more than one auto var inside single statement, because that is a rewriter, not a true compiler. So all other vars get the type of the first one.
