View Issue Details

IDProjectCategoryView StatusLast Update
0000769LDMud 3.5LPC Compiler/Preprocessorpublic2018-01-30 03:59
Reporterzesstra Assigned Tozesstra  
PrioritynormalSeverityminorReproducibilityN/A
Status resolvedResolutionfixed 
Target Version3.5.0Fixed in Version3.5.0 
Summary0000769: String storage in LPC compiler: hash table needlessly complex?
DescriptionThe compiler uses a short hash table (prog_string_indizes[256]) for keeping track of strings in a program. Additionally, it has a [32], where it stores which hash chains in prog_string_indizes are in use. It decides this like this:
  /* Bitflags showing which entries in prog_string_indizes[] are valid:
   * if (_tags[n] & (1 << b)) then _indizes[n*8 + b] is valid.
   */

I actually think this is needlessly complicated. It could just store -1 in prog_string_indizes for unused entries/chains.

My guess is that in former times the coder did not want to initialize the 256-long hash table and did initialize the 32-long prog_string_tags table instead (anyone with a better guess?). However, this assumption is not necessarily true. On my machine memset() takes actually longer to write 32 bytes than to write 256 bytes (x86_64, on x86 the 32 bytes are written marginally faster than 256). And besides the more complex code the prices is to do two calculations each time a string is searched (granted: they are fast and simple).

I tend to remove this prog_string_tags, but I would like to hear some opinions.
TagsNo tags attached.

Activities

Coogan

2011-02-24 00:16

reporter   ~0002031

Who's opinions do you want to hear? I doubt that more than a handful of persons know the driver that good from the inside.

zesstra

2011-02-25 09:19

administrator   ~0002044

Sometimes someone remembers a specific reason. ;-)

lars

2011-02-26 01:55

reporter   ~0002045

I don't know the exact reason either, but this may have been a micro-optimization aimed at reducing the amount of data read from memory when searching for a hash spot. Given the architecture changes over the last 20 years, the original reasoning (whatever it was) may no longer apply.

I suggest you benchmark the code with a realistic pool of strings to hash, both with and without the tags. If there's no discernable difference in speed, I don't remember any need to keep prog_string_tags.

(Disclaimer: I haven't looked at the code for several years now)

zesstra

2012-06-06 22:17

administrator   ~0002134

Fix committed in revision cf34204e7f9322d3c9fc5f16628e11c05ac13b3a to master branch (see changeset 854 for details). Thank you for reporting!

zesstra

2018-01-29 18:59

administrator   ~0002325

Fix committed in revision cf34204e7f9322d3c9fc5f16628e11c05ac13b3a to master branch (see changeset 1532 for details). Thank you for reporting!

zesstra

2018-01-29 21:57

administrator   ~0002376

Fix committed in revision cf34204e7f9322d3c9fc5f16628e11c05ac13b3a to master branch (see changeset 2862 for details). Thank you for reporting!

zesstra

2018-01-30 03:59

administrator   ~0002427

Fix committed in revision cf34204e7f9322d3c9fc5f16628e11c05ac13b3a to master branch (see changeset 3945 for details). Thank you for reporting!

Issue History

Date Modified Username Field Change
2011-01-12 21:35 zesstra New Issue
2011-01-12 21:36 zesstra Assigned To => zesstra
2011-01-12 21:36 zesstra Status new => feedback
2011-02-24 00:16 Coogan Note Added: 0002031
2011-02-25 09:19 zesstra Note Added: 0002044
2011-02-25 09:19 zesstra Status feedback => assigned
2011-02-26 01:55 lars Note Added: 0002045
2012-06-06 22:17 zesstra Source_changeset_attached => ldmud.git master cf34204e
2012-06-06 22:17 zesstra Note Added: 0002134
2012-06-06 22:17 zesstra Status assigned => resolved
2012-06-06 22:17 zesstra Resolution open => fixed
2012-06-06 22:24 zesstra Fixed in Version => 3.5.0
2018-01-29 18:59 zesstra Source_changeset_attached => ldmud.git master cf34204e
2018-01-29 18:59 zesstra Note Added: 0002325
2018-01-29 21:57 zesstra Source_changeset_attached => ldmud.git master cf34204e
2018-01-29 21:57 zesstra Note Added: 0002376
2018-01-30 03:59 zesstra Source_changeset_attached => ldmud.git master cf34204e
2018-01-30 03:59 zesstra Note Added: 0002427