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

Issue 583390043: Simplify and speed up uniquify (Closed)

Can't Edit
Can't Publish+Mail
Start Review
Created:
4 years, 2 months ago by hanwenn
Modified:
4 years, 2 months ago
Reviewers:
dak, dan, Dan Eble
CC:
lilypond-devel_gnu.org
Visibility:
Public.

Description

Simplify and speed up uniquify Previously we sorted the array twice. Instead, we use a hash set. This makes the procedure O(N) rather than O(N log N).

Patch Set 1 #

Total comments: 2

Patch Set 2 : vsize #

Patch Set 3 : dan eble #

Unified diffs Side-by-side diffs Delta from patch set Stats (+11 lines, -42 lines) Patch
M lily/grob.cc View 1 2 2 chunks +11 lines, -42 lines 0 comments Download

Messages

Total messages: 12
dak
Not sure about the speedup (we might have small sizes often enough that the constant ...
4 years, 2 months ago (2020-01-24 13:29:34 UTC) #1
hanwenn
On 2020/01/24 13:29:34, dak wrote: > Not sure about the speedup (we might have small ...
4 years, 2 months ago (2020-01-24 14:06:22 UTC) #2
Dan Eble
On 2020/01/24 14:06:22, hanwenn wrote: > If the allocation cost becomes problematic, we can use ...
4 years, 2 months ago (2020-01-24 14:11:59 UTC) #3
dak
On 2020/01/24 14:11:59, Dan Eble wrote: > On 2020/01/24 14:06:22, hanwenn wrote: > > If ...
4 years, 2 months ago (2020-01-24 15:17:02 UTC) #4
dak
https://codereview.appspot.com/583390043/diff/551390044/lily/grob.cc File lily/grob.cc (right): https://codereview.appspot.com/583390043/diff/551390044/lily/grob.cc#newcode971 lily/grob.cc:971: int j = 0; vsize j = 0; :-)
4 years, 2 months ago (2020-01-24 15:17:13 UTC) #5
hanwenn
vsize
4 years, 2 months ago (2020-01-24 15:22:33 UTC) #6
hanwenn
https://codereview.appspot.com/583390043/diff/551390044/lily/grob.cc File lily/grob.cc (right): https://codereview.appspot.com/583390043/diff/551390044/lily/grob.cc#newcode971 lily/grob.cc:971: int j = 0; On 2020/01/24 15:17:13, dak wrote: ...
4 years, 2 months ago (2020-01-24 15:23:45 UTC) #7
Dan Eble
On 2020/01/24 15:17:02, dak wrote: > On 2020/01/24 14:11:59, Dan Eble wrote: > > On ...
4 years, 2 months ago (2020-01-24 15:50:22 UTC) #8
dak
On 2020/01/24 15:50:22, Dan Eble wrote: > On 2020/01/24 15:17:02, dak wrote: > > On ...
4 years, 2 months ago (2020-01-24 16:11:38 UTC) #9
dan_faithful.be
On Jan 24, 2020, at 11:11, dak@gnu.org wrote: >> Don't assume the hash function is ...
4 years, 2 months ago (2020-01-24 16:29:51 UTC) #10
hanwenn
dan eble
4 years, 2 months ago (2020-01-24 17:24:37 UTC) #11
hanwenn
4 years, 2 months ago (2020-01-25 12:20:37 UTC) #12
On 2020/01/24 15:50:22, Dan Eble wrote:
> On 2020/01/24 15:17:02, dak wrote:
> > On 2020/01/24 14:11:59, Dan Eble wrote:
> > > On 2020/01/24 14:06:22, hanwenn wrote:
> > > > If the allocation cost becomes problematic, we can use another hashmap
> > > instead.
> > > 
> > > "We" could profile it and know before pushing whether it is worth it.
> > 
> > I don't think that this is really performance-critical.
> 
> I accept your informed intuition, but I also have more suggestions.
> 
> Don't assume the hash function is perfect: create the table with more buckets,
> say 2*size.
> 
> Instead of calling find() then insert(), just call insert() and check whether
it
> worked, something like this (untested):
> 
>     if (seen.insert(grobs[i]).second)
>       grobs[j++] = grobs[i];
> 
> https://en.cppreference.com/w/cpp/container/unordered_set/insert

Done.
Sign in to reply to this message.

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