Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(31)

Issue 559790043: Reimplement Scheme_hash_table using linear probing.

Can't Edit
Can't Publish+Mail
Start Review
Created:
3 years, 11 months ago by hanwenn
Modified:
3 years, 11 months ago
Reviewers:
dak, hahnjo
CC:
lilypond-devel_gnu.org
Visibility:
Public.

Description

Reimplement Scheme_hash_table using linear probing. Add a unit-test and micro-benchmark, called from input/regression/scheme-unit-test.ly The GUILE hash table implementation uses conflict resolution by chaining. This means that hash lookups involve walking linked lists, which is both relatively slow on access, and on GC tracing (the CPU cannot prefetch the next list item). The micro-benchmark for lookup shows a 1.5x - 2x speedup compared to GUILE's hashtables. The resizing strategy is to double the size if the load factor reaches 50%, making for average load of around 1/3. Hence, compared to chaining, we have 50% more memory overhead, measured in number of bytes. This is not implemented using STL hash_map, as that is specified by the standard to use chaining for conflict resolution. ( https://stackoverflow.com/questions/21518704/how-does-c-stl-unordered-map-resolve-collisions) This could be contributed to GUILE, but is kept here for simplicity of deployment (improvements would likely go into GUILE 3.2 rather than GUILE 1.8).

Patch Set 1 #

Total comments: 20

Patch Set 2 : dak comments #

Patch Set 3 : fixes #

Unified diffs Side-by-side diffs Delta from patch set Stats (+484 lines, -45 lines) Patch
A input/regression/scheme-unit-test.ly View 1 chunk +6 lines, -0 lines 0 comments Download
M lily/all-font-metrics.cc View 1 2 1 chunk +1 line, -2 lines 0 comments Download
A lily/include/benchmark-timestamp.hh View 1 1 chunk +60 lines, -0 lines 0 comments Download
M lily/include/scm-hash.hh View 1 2 2 chunks +71 lines, -9 lines 0 comments Download
M lily/include/smobs.hh View 1 2 1 chunk +0 lines, -1 line 0 comments Download
M lily/scm-hash.cc View 1 2 1 chunk +346 lines, -33 lines 0 comments Download

Messages

Total messages: 11
dak
I don't see the point in reinventing the wheel. This functionality is provided both by ...
3 years, 11 months ago (2020-04-10 21:43:29 UTC) #1
hanwenn
> In addition, I don't think that it is used to a degree where it ...
3 years, 11 months ago (2020-04-11 05:37:39 UTC) #2
hanwenn
dak comments
3 years, 11 months ago (2020-04-11 05:42:03 UTC) #3
hahnjo
On 2020/04/11 05:37:39, hanwenn wrote: > > In addition, I don't think that it is ...
3 years, 11 months ago (2020-04-11 11:05:28 UTC) #4
dak
On 2020/04/11 05:37:39, hanwenn wrote: > > In addition, I don't think that it is ...
3 years, 11 months ago (2020-04-11 11:15:46 UTC) #5
hanwenn
On Sat, Apr 11, 2020 at 1:05 PM <jonas.hahnfeld@gmail.com> wrote: > > On 2020/04/11 05:37:39, ...
3 years, 11 months ago (2020-04-11 11:36:16 UTC) #6
dak
On 2020/04/11 11:36:16, hanwenn wrote: > On Sat, Apr 11, 2020 at 1:05 PM <mailto:jonas.hahnfeld@gmail.com> ...
3 years, 11 months ago (2020-04-11 11:46:40 UTC) #7
hanwenn
fixes
3 years, 11 months ago (2020-04-12 10:42:55 UTC) #8
hanwenn
this should probably not be merged, given the inability to demonstrate speed savings. But I'm ...
3 years, 11 months ago (2020-04-12 11:05:14 UTC) #9
hahnjo
On 2020/04/12 11:05:14, hanwenn wrote: > this should probably not be merged, given the inability ...
3 years, 11 months ago (2020-04-14 06:57:51 UTC) #10
hanwenn
3 years, 11 months ago (2020-04-14 07:24:54 UTC) #11
Sure.

On Tue, Apr 14, 2020 at 8:57 AM <jonas.hahnfeld@gmail.com> wrote:
>
> On 2020/04/12 11:05:14, hanwenn wrote:
> > this should probably not be merged, given the inability to demonstrate
> speed
> > savings.  But I'm uploading the latest version to not leave bugs in
> the public
> > record.
>
> Shall we put the patch on Needs_work to avoid progressing in the usual
> process?
>
> https://codereview.appspot.com/559790043/



-- 
Han-Wen Nienhuys - hanwenn@gmail.com - http://www.xs4all.nl/~hanwen
Sign in to reply to this message.

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b