TrueCloudLab
/
hrw
20
0
Fork 5
Code Issues 1 Pull Requests Releases 2 Activity

Some optimizations for HRW sort #8

Merged
fyrchik merged 1 commits from fyrchik/hrw:optimize-hrw into master 2023-07-26 21:08:01 +00:00
Conversation 0 Commits 1 Files Changed 2
fyrchik commented 2023-06-01 18:41:13 +00:00
Owner

Total value of all optimizations in this PR (don't look at the last line, there was 100 in master and fixed 1000 in this PR):

goos: linux
goarch: amd64
pkg: git.frostfs.info/TrueCloudLab/hrw
cpu: 11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz
                                              │      0      │                    7                     │
                                              │   sec/op    │    sec/op      vs base                   │
SortHashersByValue_Typed_fnv_10-8               596.2n ± 4%    166.9n ±  9%   -72.01% (p=0.000 n=10)
SortHashersByValue_Typed_fnv_100-8              4.453µ ± 2%    1.297µ ±  6%   -70.88% (p=0.000 n=10)
SortHashersByValue_Typed_fnv_1000-8             41.58µ ± 4%    12.42µ ± 10%   -70.13% (p=0.000 n=10)
SortHashersByWeightValueTyped_fnv_10-8          624.5n ± 2%    180.8n ±  4%   -71.06% (p=0.000 n=10)
SortHashersByWeightValueTyped_fnv_100-8         4.593µ ± 2%    1.378µ ±  5%   -70.01% (p=0.000 n=10)
SortHashersByWeightValueTyped_fnv_1000-8        4.896µ ± 8%   12.798µ ±  4%  +161.42% (p=0.000 n=10)
geomean                                         4.668µ         1.430µ         -57.95%                ¹
¹ benchmark set differs from baseline; geomeans may not be comparable

                                              │       0       │                   7                    │
                                              │     B/op      │     B/op      vs base                  │
SortHashersByValue_Typed_fnv_10-8                  584.0 ± 0%     144.0 ± 0%  -75.34% (p=0.000 n=10)
SortHashersByValue_Typed_fnv_100-8                4472.0 ± 0%     960.0 ± 0%  -78.53% (p=0.000 n=10)
SortHashersByValue_Typed_fnv_1000-8             39.805Ki ± 0%   8.062Ki ± 0%  -79.74% (p=0.000 n=10)
SortHashersByWeightValueTyped_fnv_10-8             600.0 ± 0%     144.0 ± 0%  -76.00% (p=0.000 n=10)
SortHashersByWeightValueTyped_fnv_100-8           4488.0 ± 0%     960.0 ± 0%  -78.61% (p=0.000 n=10)
SortHashersByWeightValueTyped_fnv_1000-8         4.383Ki ± 0%   8.062Ki ± 0%  +83.96% (p=0.000 n=10)
geomean                                          3.742Ki        1.021Ki       -68.31%                ¹
¹ benchmark set differs from baseline; geomeans may not be comparable

                                              │       0       │                  7                   │
                                              │   allocs/op   │ allocs/op   vs base                  │
SortHashersByValue_Typed_fnv_10-8                 17.000 ± 0%   2.000 ± 0%  -88.24% (p=0.000 n=10)
SortHashersByValue_Typed_fnv_100-8               107.000 ± 0%   2.000 ± 0%  -98.13% (p=0.000 n=10)
SortHashersByValue_Typed_fnv_1000-8             1007.000 ± 0%   2.000 ± 0%  -99.80% (p=0.000 n=10)
SortHashersByWeightValueTyped_fnv_10-8            17.000 ± 0%   2.000 ± 0%  -88.24% (p=0.000 n=10)
SortHashersByWeightValueTyped_fnv_100-8          107.000 ± 0%   2.000 ± 0%  -98.13% (p=0.000 n=10)
SortHashersByWeightValueTyped_fnv_1000-8         107.000 ± 0%   2.000 ± 0%  -98.13% (p=0.000 n=10)
geomean                                            115.3        2.000       -97.62%                ¹
¹ benchmark set differs from baseline; geomeans may not be comparable
Total value of all optimizations in this PR (don't look at the last line, there was 100 in master and fixed 1000 in this PR): ``` goos: linux goarch: amd64 pkg: git.frostfs.info/TrueCloudLab/hrw cpu: 11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz │ 0 │ 7 │ │ sec/op │ sec/op vs base │ SortHashersByValue_Typed_fnv_10-8 596.2n ± 4% 166.9n ± 9% -72.01% (p=0.000 n=10) SortHashersByValue_Typed_fnv_100-8 4.453µ ± 2% 1.297µ ± 6% -70.88% (p=0.000 n=10) SortHashersByValue_Typed_fnv_1000-8 41.58µ ± 4% 12.42µ ± 10% -70.13% (p=0.000 n=10) SortHashersByWeightValueTyped_fnv_10-8 624.5n ± 2% 180.8n ± 4% -71.06% (p=0.000 n=10) SortHashersByWeightValueTyped_fnv_100-8 4.593µ ± 2% 1.378µ ± 5% -70.01% (p=0.000 n=10) SortHashersByWeightValueTyped_fnv_1000-8 4.896µ ± 8% 12.798µ ± 4% +161.42% (p=0.000 n=10) geomean 4.668µ 1.430µ -57.95% ¹ ¹ benchmark set differs from baseline; geomeans may not be comparable │ 0 │ 7 │ │ B/op │ B/op vs base │ SortHashersByValue_Typed_fnv_10-8 584.0 ± 0% 144.0 ± 0% -75.34% (p=0.000 n=10) SortHashersByValue_Typed_fnv_100-8 4472.0 ± 0% 960.0 ± 0% -78.53% (p=0.000 n=10) SortHashersByValue_Typed_fnv_1000-8 39.805Ki ± 0% 8.062Ki ± 0% -79.74% (p=0.000 n=10) SortHashersByWeightValueTyped_fnv_10-8 600.0 ± 0% 144.0 ± 0% -76.00% (p=0.000 n=10) SortHashersByWeightValueTyped_fnv_100-8 4488.0 ± 0% 960.0 ± 0% -78.61% (p=0.000 n=10) SortHashersByWeightValueTyped_fnv_1000-8 4.383Ki ± 0% 8.062Ki ± 0% +83.96% (p=0.000 n=10) geomean 3.742Ki 1.021Ki -68.31% ¹ ¹ benchmark set differs from baseline; geomeans may not be comparable │ 0 │ 7 │ │ allocs/op │ allocs/op vs base │ SortHashersByValue_Typed_fnv_10-8 17.000 ± 0% 2.000 ± 0% -88.24% (p=0.000 n=10) SortHashersByValue_Typed_fnv_100-8 107.000 ± 0% 2.000 ± 0% -98.13% (p=0.000 n=10) SortHashersByValue_Typed_fnv_1000-8 1007.000 ± 0% 2.000 ± 0% -99.80% (p=0.000 n=10) SortHashersByWeightValueTyped_fnv_10-8 17.000 ± 0% 2.000 ± 0% -88.24% (p=0.000 n=10) SortHashersByWeightValueTyped_fnv_100-8 107.000 ± 0% 2.000 ± 0% -98.13% (p=0.000 n=10) SortHashersByWeightValueTyped_fnv_1000-8 107.000 ± 0% 2.000 ± 0% -98.13% (p=0.000 n=10) geomean 115.3 2.000 -97.62% ¹ ¹ benchmark set differs from baseline; geomeans may not be comparable ```
fyrchik force-pushed optimize-hrw from f1874161d6 to 6ec195b0c9 2023-06-01 18:43:01 +00:00 Compare
fyrchik requested review from storage-core-committers 2023-06-01 18:43:14 +00:00
fyrchik requested review from storage-core-developers 2023-06-01 18:43:14 +00:00
fyrchik requested review from alexvanin 2023-06-01 18:43:32 +00:00
fyrchik requested review from storage-services-committers 2023-06-01 18:43:58 +00:00
fyrchik requested review from storage-services-developers 2023-06-01 18:43:58 +00:00
dstepanov-yadro reviewed 2023-06-02 07:34:05 +00:00
hrw.go Outdated
@ -36,0 +44,4 @@
if s.asc {
return s.dist[i] < s.dist[j]
} else {
return s.dist[i] > s.dist[j]
dstepanov-yadro commented 2023-06-02 07:34:05 +00:00
Collaborator

Redundant else

Redundant `else`
fyrchik commented 2023-06-02 07:57:28 +00:00
Poster
Owner

Fixed

Fixed
dstepanov-yadro marked this conversation as resolved
dstepanov-yadro reviewed 2023-06-02 07:35:47 +00:00
hrw.go Outdated
@ -112,2 +141,3 @@
dist[i] = distance(slice[i].Hash(), hash)
}
sortByWeight(len(slice), false, rule, weights, hash, swap)
sortHasherByDistance(slice, false, dist)
dstepanov-yadro commented 2023-06-02 07:35:47 +00:00
Collaborator

return?

return?
fyrchik commented 2023-06-02 07:54:44 +00:00
Poster
Owner

Fixed

Fixed
dstepanov-yadro marked this conversation as resolved
dstepanov-yadro reviewed 2023-06-02 07:39:40 +00:00
hrw.go Outdated
@ -115,0 +154,4 @@
sort.Sort(&hasherSorter[T, float64]{
slice: slice,
dist: dist,
asc: false,
dstepanov-yadro commented 2023-06-02 07:39:40 +00:00
Collaborator

Why asc: false, but sortHasherByDistance has asc: true.

Why `asc: false`, but `sortHasherByDistance` has `asc: true`.
fyrchik commented 2023-06-02 07:56:38 +00:00
Poster
Owner

It is intentional, if you look at the previous implementation, we sort with dist[i] < dist[j] for distance and the other way here. In the latter case it is transformed, see line 151.

It is intentional, if you look at the previous implementation, we sort with `dist[i] < dist[j]` for distance and the other way here. In the latter case it is transformed, see line 151.
dstepanov-yadro marked this conversation as resolved
fyrchik force-pushed optimize-hrw from 6ec195b0c9 to 16a7740ccd 2023-06-02 08:00:45 +00:00 Compare
dstepanov-yadro approved these changes 2023-06-02 08:18:05 +00:00
acid-ant approved these changes 2023-06-02 08:34:13 +00:00
alexvanin approved these changes 2023-06-02 08:37:58 +00:00
fyrchik merged commit 16a7740ccd into master 2023-06-02 09:21:37 +00:00
fyrchik deleted branch optimize-hrw 2023-06-02 09:21:38 +00:00
Sign in to join this conversation.
Reviewers
No reviewers
dstepanov-yadro
acid-ant
alexvanin
TrueCloudLab/storage-services-developers
Labels
Clear labels   
P0

Highest   
P1

High   
P2

Medium   
P3

Low   
good first issue

Good for newcomers
  
Infrastructure

Infrastructure, Automation, CI/CD or DevOps related stuff   
blocked

The issue or PR is blocked by something   
bug

Something is not working   
config

Configuration format update or breaking change   
discussion

Talking about something in order to reach a decision or to exchange ideas   
documentation

Documentation related   
duplicate

This issue or pull request already exists   
enhancement

New feature   
go

Language features adoption   
help wanted

Extra attention is needed   
internal
   
invalid

Something is wrong   
kludge

This is a kludge and we know it   
observability

Related to metrics, tracing and logs   
perfomance

Perfomance related   
question

More information is needed   
refactoring

Refactoring   
wontfix

This won't be fixed
No Label
P0
P1
P2
P3
good first issue
Infrastructure
blocked
bug
config
discussion
documentation
duplicate
enhancement
go
help wanted
internal
invalid
kludge
observability
perfomance
question
refactoring
wontfix
Milestone
Clear milestone
No items
No Milestone
Assignees
Clear assignees
No Assignees
4 Participants
Notifications
Due Date
The due date is invalid or out of range. Please use the format 'yyyy-mm-dd'.

No due date set.

Dependencies

No dependencies set.

Reference: TrueCloudLab/hrw#8
There is no content yet.
Delete Branch "fyrchik/hrw:optimize-hrw"

Deleting a branch is permanent. Although the deleted branch may exist for a short time before cleaning up, in most cases it CANNOT be undone. Continue?