[#8] hrw: Introduce StringHash() for hashing strings directly

```
goos: linux
goarch: amd64
pkg: git.frostfs.info/TrueCloudLab/hrw
cpu: 11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz
                                         │      6      │                  7                   │
                                         │   sec/op    │    sec/op     vs base                │
SortHashersByValue_Typed_fnv_10-8          248.8n ± 1%   166.9n ±  9%  -32.93% (p=0.000 n=10)
SortHashersByValue_Typed_fnv_100-8         2.195µ ± 6%   1.297µ ±  6%  -40.93% (p=0.000 n=10)
SortHashersByValue_Typed_fnv_1000-8        22.47µ ± 4%   12.42µ ± 10%  -44.73% (p=0.000 n=10)
SortHashersByWeightValueTyped_fnv_10-8     301.7n ± 6%   180.8n ±  4%  -40.09% (p=0.000 n=10)
SortHashersByWeightValueTyped_fnv_100-8    2.526µ ± 1%   1.378µ ±  5%  -45.47% (p=0.000 n=10)
SortHashersByWeightValueTyped_fnv_1000-8   24.37µ ± 2%   12.80µ ±  4%  -47.48% (p=0.000 n=10)
geomean                                    2.472µ        1.430µ        -42.13%

                                         │      6       │                   7                   │
                                         │     B/op     │     B/op      vs base                 │
SortHashersByValue_Typed_fnv_10-8            144.0 ± 0%     144.0 ± 0%       ~ (p=1.000 n=10) ¹
SortHashersByValue_Typed_fnv_100-8           960.0 ± 0%     960.0 ± 0%       ~ (p=1.000 n=10) ¹
SortHashersByValue_Typed_fnv_1000-8        8.062Ki ± 0%   8.062Ki ± 0%       ~ (p=1.000 n=10) ¹
SortHashersByWeightValueTyped_fnv_10-8       144.0 ± 0%     144.0 ± 0%       ~ (p=1.000 n=10) ¹
SortHashersByWeightValueTyped_fnv_100-8      960.0 ± 0%     960.0 ± 0%       ~ (p=1.000 n=10) ¹
SortHashersByWeightValueTyped_fnv_1000-8   8.062Ki ± 0%   8.062Ki ± 0%       ~ (p=1.000 n=10) ¹
geomean                                    1.021Ki        1.021Ki       +0.00%
¹ all samples are equal

                                         │     6      │                  7                  │
                                         │ allocs/op  │ allocs/op   vs base                 │
SortHashersByValue_Typed_fnv_10-8          2.000 ± 0%   2.000 ± 0%       ~ (p=1.000 n=10) ¹
SortHashersByValue_Typed_fnv_100-8         2.000 ± 0%   2.000 ± 0%       ~ (p=1.000 n=10) ¹
SortHashersByValue_Typed_fnv_1000-8        2.000 ± 0%   2.000 ± 0%       ~ (p=1.000 n=10) ¹
SortHashersByWeightValueTyped_fnv_10-8     2.000 ± 0%   2.000 ± 0%       ~ (p=1.000 n=10) ¹
SortHashersByWeightValueTyped_fnv_100-8    2.000 ± 0%   2.000 ± 0%       ~ (p=1.000 n=10) ¹
SortHashersByWeightValueTyped_fnv_1000-8   2.000 ± 0%   2.000 ± 0%       ~ (p=1.000 n=10) ¹
geomean                                    2.000        2.000       +0.00%
¹ all samples are equal
```

Signed-off-by: Evgenii Stratonikov <e.stratonikov@yadro.com>

.gitlint

@@ -0,0 +1,10 @@
+[general]
+fail-without-commits=true
+contrib=CC1
+
+[title-match-regex]
+regex=^\[\#[0-9]+\]\s
+
+[ignore-by-title]
+regex=^Release(.*)
+ignore=title-match-regex

.pre-commit-config.yaml

@@ -0,0 +1,30 @@
+ci:
+  autofix_prs: false
+
+repos:
+  - repo: https://github.com/pre-commit/pre-commit-hooks
+    rev: v4.4.0
+    hooks:
+    - id: check-added-large-files
+    - id: check-case-conflict
+    - id: check-executables-have-shebangs
+    - id: check-shebang-scripts-are-executable
+    - id: check-merge-conflict
+    - id: check-json
+    - id: check-xml
+    - id: check-yaml
+    - id: trailing-whitespace
+      args: [--markdown-linebreak-ext=md]
+    - id: end-of-file-fixer
+      exclude: ".key$"
+
+  - repo: https://github.com/golangci/golangci-lint
+    rev: v1.51.2
+    hooks:
+    - id: golangci-lint
+
+  - repo: https://github.com/jorisroovers/gitlint
+    rev:  v0.18.0
+    hooks:
+      - id: gitlint
+        stages: [commit-msg]

.travis.yml

@@ -1,17 +0,0 @@
-language: go
-go:
-  - 1.11.x
-  - 1.12.x
-env:
-  - GO111MODULE=on
-install:
-  - go get -v golang.org/x/lint/golint
-  - go mod tidy -v
-script:
-  - golint -set_exit_status ./...
-  - go test -race -coverprofile=coverage.txt -covermode=atomic ./...
-after_success:
-  - bash <(curl -s https://codecov.io/bash)
-matrix:
-  allow_failures:
-    - go: tip

README.md

@@ -14,25 +14,37 @@
 ## Benchmark:
 
 ```
-BenchmarkSort_fnv_10-8                           5000000               365 ns/op             224 B/op          3 allocs/op
+BenchmarkSort_fnv_10-8                                           4812801               240.9 ns/op           216 B/op          4 allocs/op
-BenchmarkSort_fnv_100-8                           300000              5261 ns/op            1856 B/op          3 allocs/op
+BenchmarkSort_fnv_100-8                                           434767              2600 ns/op            1848 B/op          4 allocs/op
-BenchmarkSort_fnv_1000-8                           10000            119462 ns/op           16448 B/op          3 allocs/op
+BenchmarkSort_fnv_1000-8                                           20428             66116 ns/op           16440 B/op          4 allocs/op
-BenchmarkSortByIndex_fnv_10-8                    3000000               546 ns/op             384 B/op          7 allocs/op
+BenchmarkSortByIndex_fnv_10-8                                    2505410               486.5 ns/op           352 B/op          7 allocs/op
-BenchmarkSortByIndex_fnv_100-8                    200000              5965 ns/op            2928 B/op          7 allocs/op
+BenchmarkSortByIndex_fnv_100-8                                    254556              4697 ns/op            1984 B/op          7 allocs/op
-BenchmarkSortByIndex_fnv_1000-8                    10000            127732 ns/op           25728 B/op          7 allocs/op
+BenchmarkSortByIndex_fnv_1000-8                                    13581             88334 ns/op           16576 B/op          7 allocs/op
-BenchmarkSortByValue_fnv_10-8                    2000000               962 ns/op             544 B/op         17 allocs/op
+BenchmarkSortByValue_fnv_10-8                                    1761030               682.1 ns/op           592 B/op         18 allocs/op
-BenchmarkSortByValue_fnv_100-8                    200000              9604 ns/op            4528 B/op        107 allocs/op
+BenchmarkSortByValue_fnv_100-8                                    258838              4675 ns/op            4480 B/op        108 allocs/op
-BenchmarkSortByValue_fnv_1000-8                    10000            111741 ns/op           41728 B/op       1007 allocs/op
+BenchmarkSortByValue_fnv_1000-8                                    27027             44649 ns/op           40768 B/op       1008 allocs/op
+BenchmarkSortHashersByValue_Reflection_fnv_10-8                  1013560              1249 ns/op             768 B/op         29 allocs/op
+BenchmarkSortHashersByValue_Reflection_fnv_100-8                  106029             11414 ns/op            6096 B/op        209 allocs/op
+BenchmarkSortHashersByValue_Reflection_fnv_1000-8                  10000            108977 ns/op           56784 B/op       2009 allocs/op
+BenchmarkSortHashersByValue_Typed_fnv_10-8                       1577814               700.3 ns/op           584 B/op         17 allocs/op
+BenchmarkSortHashersByValue_Typed_fnv_100-8                       215938              5024 ns/op            4472 B/op        107 allocs/op
+BenchmarkSortHashersByValue_Typed_fnv_1000-8                       24447             46889 ns/op           40760 B/op       1007 allocs/op
 
-BenchmarkSortByWeight_fnv_10-8                   3000000               501 ns/op             320 B/op          4 allocs/op
+BenchmarkSortByWeight_fnv_10-8                                   2924833               370.6 ns/op           448 B/op          8 allocs/op
-BenchmarkSortByWeight_fnv_100-8                   200000              8495 ns/op            2768 B/op          4 allocs/op
+BenchmarkSortByWeight_fnv_100-8                                   816069              1516 ns/op            2896 B/op          8 allocs/op
-BenchmarkSortByWeight_fnv_1000-8                   10000            197880 ns/op           24656 B/op          4 allocs/op
+BenchmarkSortByWeight_fnv_1000-8                                   80391             17478 ns/op           24784 B/op          8 allocs/op
-BenchmarkSortByWeightIndex_fnv_10-8              2000000               702 ns/op             480 B/op          8 allocs/op
+BenchmarkSortByWeightIndex_fnv_10-8                              1945612               550.3 ns/op           368 B/op          7 allocs/op
-BenchmarkSortByWeightIndex_fnv_100-8              200000              9338 ns/op            3840 B/op          8 allocs/op
+BenchmarkSortByWeightIndex_fnv_100-8                              140473              8084 ns/op            2000 B/op          7 allocs/op
-BenchmarkSortByWeightIndex_fnv_1000-8              10000            204669 ns/op           33936 B/op          8 allocs/op
+BenchmarkSortByWeightIndex_fnv_1000-8                               5518            200949 ns/op           16592 B/op          7 allocs/op
-BenchmarkSortByWeightValue_fnv_10-8              1000000              1083 ns/op             640 B/op         18 allocs/op
+BenchmarkSortByWeightValue_fnv_10-8                              1305580               909.8 ns/op           608 B/op         18 allocs/op
-BenchmarkSortByWeightValue_fnv_100-8              200000             11444 ns/op            5440 B/op        108 allocs/op
+BenchmarkSortByWeightValue_fnv_100-8                              165410              6796 ns/op            4496 B/op        108 allocs/op
-BenchmarkSortByWeightValue_fnv_1000-8              10000            148471 ns/op           49936 B/op       1008 allocs/op
+BenchmarkSortByWeightValue_fnv_1000-8                              17922             78555 ns/op           40784 B/op       1008 allocs/op
+BenchmarkSortHashersByWeightValueReflection_fnv_10-8              454976              2229 ns/op             784 B/op         29 allocs/op
+BenchmarkSortHashersByWeightValueReflection_fnv_100-8              76264             15332 ns/op            6112 B/op        209 allocs/op
+BenchmarkSortHashersByWeightValueReflection_fnv_1000-8             80288             13192 ns/op            6112 B/op        209 allocs/op
+BenchmarkSortHashersByWeightValueTyped_fnv_10-8                  1433113               901.4 ns/op           600 B/op         17 allocs/op
+BenchmarkSortHashersByWeightValueTyped_fnv_100-8                  188626              5896 ns/op            4488 B/op        107 allocs/op
+BenchmarkSortHashersByWeightValueTyped_fnv_1000-8                 178131              6518 ns/op            4488 B/op        107 allocs/op
 ```
 
 ## Example
@@ -43,7 +55,7 @@ package main
 import (
 	"fmt"
 
-	"github.com/nspcc-dev/hrw"
+	"git.frostfs.info/TrueCloudLab/hrw"
 )
 
 func main() {

go.mod

@@ -1,6 +1,13 @@
-module github.com/nspcc-dev/hrw
+module git.frostfs.info/TrueCloudLab/hrw
+
+go 1.18
 
 require (
-	github.com/spaolacci/murmur3 v1.1.0
 	github.com/stretchr/testify v1.3.0
+	github.com/twmb/murmur3 v1.1.8
+)
+
+require (
+	github.com/davecgh/go-spew v1.1.0 // indirect
+	github.com/pmezard/go-difflib v1.0.0 // indirect
 )

go.sum

@@ -2,8 +2,8 @@ github.com/davecgh/go-spew v1.1.0 h1:ZDRjVQ15GmhC3fiQ8ni8+OwkZQO4DARzQgrnXU1Liz8
 github.com/davecgh/go-spew v1.1.0/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
 github.com/pmezard/go-difflib v1.0.0 h1:4DBwDE0NGyQoBHbLQYPwSUPoCMWR5BEzIk/f1lZbAQM=
 github.com/pmezard/go-difflib v1.0.0/go.mod h1:iKH77koFhYxTK1pcRnkKkqfTogsbg7gZNVY4sRDYZ/4=
-github.com/spaolacci/murmur3 v1.1.0 h1:7c1g84S4BPRrfL5Xrdp6fOJ206sU9y293DDHaoy0bLI=
-github.com/spaolacci/murmur3 v1.1.0/go.mod h1:JwIasOWyU6f++ZhiEuf87xNszmSA2myDM2Kzu9HwQUA=
 github.com/stretchr/objx v0.1.0/go.mod h1:HFkY916IF+rwdDfMAkV7OtwuqBVzrE8GR6GFx+wExME=
 github.com/stretchr/testify v1.3.0 h1:TivCn/peBQ7UY8ooIcPgZFpTNSz0Q2U6UrFlUfqbe0Q=
 github.com/stretchr/testify v1.3.0/go.mod h1:M5WIy9Dh21IEIfnGCwXGc5bZfKNJtfHm1UVUgZn+9EI=
+github.com/twmb/murmur3 v1.1.8 h1:8Yt9taO/WN3l08xErzjeschgZU2QSrwm1kclYq+0aRg=
+github.com/twmb/murmur3 v1.1.8/go.mod h1:Qq/R7NUyOfr65zD+6Q5IHKsJLwP7exErjN6lyyq3OSQ=

hrw.go

@@ -5,27 +5,27 @@ package hrw
 import (
 	"encoding/binary"
 	"errors"
+	"math"
 	"reflect"
 	"sort"
 
-	"github.com/spaolacci/murmur3"
+	"github.com/twmb/murmur3"
 )
 
 type (
-	swapper func(i, j int)
-
 	// Hasher interface used by SortSliceByValue
 	Hasher interface{ Hash() uint64 }
 
-	hashed struct {
+	sorter struct {
-		length   int
+		l    int
-		sorted   []uint64
+		less func(i, j int) bool
-		distance []uint64
+		swap func(i, j int)
 	}
 
-	weighted struct {
+	hasherSorter[T Hasher, N interface{ ~uint64 | ~float64 }] struct {
-		h      hashed
+		slice []T
-		normal []float64 // normalized input weights
+		dist  []N
+		asc   bool
 	}
 )
 
@@ -35,6 +35,22 @@ const (
 	NormalizedMinWeight = 0.0
 )
 
+func (s *sorter) Len() int           { return s.l }
+func (s *sorter) Less(i, j int) bool { return s.less(i, j) }
+func (s *sorter) Swap(i, j int)      { s.swap(i, j) }
+
+func (s *hasherSorter[T, N]) Len() int { return len(s.slice) }
+func (s *hasherSorter[T, N]) Less(i, j int) bool {
+	if s.asc {
+		return s.dist[i] < s.dist[j]
+	}
+	return s.dist[i] > s.dist[j]
+}
+func (s *hasherSorter[T, N]) Swap(i, j int) {
+	s.slice[i], s.slice[j] = s.slice[j], s.slice[i]
+	s.dist[i], s.dist[j] = s.dist[j], s.dist[i]
+}
+
 func distance(x uint64, y uint64) uint64 {
 	acc := x ^ y
 	// here used mmh3 64 bit finalizer
@@ -47,83 +63,38 @@ func distance(x uint64, y uint64) uint64 {
 	return acc
 }
 
-func (h hashed) Len() int           { return h.length }
-func (h hashed) Less(i, j int) bool { return h.distance[i] < h.distance[j] }
-func (h hashed) Swap(i, j int) {
-	h.sorted[i], h.sorted[j] = h.sorted[j], h.sorted[i]
-	h.distance[i], h.distance[j] = h.distance[j], h.distance[i]
-}
-
-func (w weighted) Len() int { return w.h.length }
-func (w weighted) Less(i, j int) bool {
-	// `maxUint64 - distance` makes the shorter distance more valuable
-	// it is necessary for operation with normalized values
-	wi := float64(^uint64(0)-w.h.distance[i]) * w.normal[i]
-	wj := float64(^uint64(0)-w.h.distance[j]) * w.normal[j]
-	return wi > wj // higher distance must be placed lower to be first
-}
-func (w weighted) Swap(i, j int) { w.normal[i], w.normal[j] = w.normal[j], w.normal[i]; w.h.Swap(i, j) }
-
 // Hash uses murmur3 hash to return uint64
 func Hash(key []byte) uint64 {
 	return murmur3.Sum64(key)
 }
 
+// StringHash uses murmur3 hash to return uint64
+func StringHash(key string) uint64 {
+	return murmur3.StringSum64(key)
+}
+
 // Sort receive nodes and hash, and sort it by distance
 func Sort(nodes []uint64, hash uint64) []uint64 {
-	var (
+	l := len(nodes)
-		l = len(nodes)
+	sorted := make([]uint64, l)
-		h = hashed{
+	dist := make([]uint64, l)
-			length:   l,
-			sorted:   make([]uint64, 0, l),
-			distance: make([]uint64, 0, l),
-		}
-	)
-
 	for i := range nodes {
-		h.sorted = append(h.sorted, uint64(i))
+		sorted[i] = uint64(i)
-		h.distance = append(h.distance, distance(nodes[i], hash))
+		dist[i] = distance(nodes[i], hash)
 	}
 
-	sort.Sort(h)
+	sort.Slice(sorted, func(i, j int) bool {
-	return h.sorted
+		return dist[sorted[i]] < dist[sorted[j]]
+	})
+	return sorted
 }
 
 // SortByWeight receive nodes, weights and hash, and sort it by distance * weight
 func SortByWeight(nodes []uint64, weights []float64, hash uint64) []uint64 {
-	// check if numbers of weights and nodes are equal
+	result := make([]uint64, len(nodes))
-	uniform := true
+	copy(nodes, result)
-	for i := range weights {
+	sortByWeight(len(nodes), false, nodes, weights, hash, reflect.Swapper(result))
-		// check if all nodes have the same distance
+	return result
-		if weights[i] != weights[0] {
-			uniform = false
-			break
-		}
-	}
-
-	l := len(nodes)
-	w := weighted{
-		h: hashed{
-			length:   l,
-			sorted:   make([]uint64, 0, l),
-			distance: make([]uint64, 0, l),
-		},
-		normal: make([]float64, l),
-	}
-
-	// if all nodes have the same distance then sort uniformly
-	if uniform || len(weights) != l {
-		return Sort(nodes, hash)
-	}
-
-	for i := range nodes {
-		w.h.sorted = append(w.h.sorted, uint64(i))
-		w.h.distance = append(w.h.distance, distance(nodes[i], hash))
-	}
-	copy(w.normal, weights)
-
-	sort.Sort(w)
-	return w.h.sorted
 }
 
 // SortSliceByValue received []T and hash to sort by value-distance
@@ -131,76 +102,89 @@ func SortSliceByValue(slice interface{}, hash uint64) {
 	rule := prepareRule(slice)
 	if rule != nil {
 		swap := reflect.Swapper(slice)
-		rule = Sort(rule, hash)
+		sortByDistance(len(rule), false, rule, hash, swap)
-		sortByRuleInverse(swap, uint64(len(rule)), rule)
 	}
 }
 
+// SortHasherSliceByValue receives []Hasher and hash to sort by value-distance.
+func SortHasherSliceByValue[T Hasher](slice []T, hash uint64) {
+	if len(slice) == 0 {
+		return
+	}
+
+	dist := make([]uint64, len(slice))
+	for i := range dist {
+		dist[i] = distance(slice[i].Hash(), hash)
+	}
+	sortHasherByDistance(slice, false, dist)
+}
+
 // SortSliceByWeightValue received []T, weights and hash to sort by value-distance * weights
 func SortSliceByWeightValue(slice interface{}, weights []float64, hash uint64) {
 	rule := prepareRule(slice)
 	if rule != nil {
 		swap := reflect.Swapper(slice)
-		rule = SortByWeight(rule, weights, hash)
+		sortByWeight(reflect.ValueOf(slice).Len(), false, rule, weights, hash, swap)
-		sortByRuleInverse(swap, uint64(len(rule)), rule)
 	}
 }
 
+// SortHasherSliceByWeightValue receives []Hasher, weights and hash to sort by value-distance * weights.
+func SortHasherSliceByWeightValue[T Hasher](slice []T, weights []float64, hash uint64) {
+	if len(slice) == 0 {
+		return
+	}
+
+	if allSameF64(weights) {
+		dist := make([]uint64, len(slice))
+		for i := range dist {
+			dist[i] = distance(slice[i].Hash(), hash)
+		}
+		sortHasherByDistance(slice, false, dist)
+		return
+	}
+
+	dist := make([]float64, len(slice))
+	for i := range dist {
+		d := distance(slice[i].Hash(), hash)
+		// `maxUint64 - distance` makes the shorter distance more valuable
+		// it is necessary for operation with normalized values
+		dist[i] = float64(^uint64(0)-d) * weights[i]
+	}
+
+	sort.Sort(&hasherSorter[T, float64]{
+		slice: slice,
+		dist:  dist,
+		asc:   false,
+	})
+}
+
+// sortHasherByDistance is similar to sortByDistance but accepts slice directly.
+func sortHasherByDistance[T Hasher](slice []T, byIndex bool, dist []uint64) {
+	sort.Sort(&hasherSorter[T, uint64]{
+		slice: slice,
+		dist:  dist,
+		asc:   true,
+	})
+}
+
 // SortSliceByIndex received []T and hash to sort by index-distance
 func SortSliceByIndex(slice interface{}, hash uint64) {
-	length := uint64(reflect.ValueOf(slice).Len())
+	length := reflect.ValueOf(slice).Len()
 	swap := reflect.Swapper(slice)
-	rule := make([]uint64, 0, length)
+	sortByDistance(length, true, nil, hash, swap)
-	for i := uint64(0); i < length; i++ {
-		rule = append(rule, i)
-	}
-	rule = Sort(rule, hash)
-	sortByRuleInverse(swap, length, rule)
 }
 
 // SortSliceByWeightIndex received []T, weights and hash to sort by index-distance * weights
 func SortSliceByWeightIndex(slice interface{}, weights []float64, hash uint64) {
-	length := uint64(reflect.ValueOf(slice).Len())
+	length := reflect.ValueOf(slice).Len()
 	swap := reflect.Swapper(slice)
-	rule := make([]uint64, 0, length)
+	sortByWeight(length, true, nil, weights, hash, swap)
-	for i := uint64(0); i < length; i++ {
-		rule = append(rule, i)
-	}
-	rule = SortByWeight(rule, weights, hash)
-	sortByRuleInverse(swap, length, rule)
-}
-
-func sortByRuleDirect(swap swapper, length uint64, rule []uint64) {
-	done := make([]bool, length)
-	for i := uint64(0); i < length; i++ {
-		if done[i] {
-			continue
-		}
-		for j := rule[i]; !done[rule[j]]; j = rule[j] {
-			swap(int(i), int(j))
-			done[j] = true
-		}
-	}
-}
-
-func sortByRuleInverse(swap swapper, length uint64, rule []uint64) {
-	done := make([]bool, length)
-	for i := uint64(0); i < length; i++ {
-		if done[i] {
-			continue
-		}
-
-		for j := i; !done[rule[j]]; j = rule[j] {
-			swap(int(j), int(rule[j]))
-			done[j] = true
-		}
-	}
 }
 
 func prepareRule(slice interface{}) []uint64 {
 	t := reflect.TypeOf(slice)
 	if t.Kind() != reflect.Slice {
-		return nil
+		panic("HRW sort expects slice, got " + t.Kind().String())
 	}
 
 	var (
@@ -279,7 +263,7 @@ func prepareRule(slice interface{}) []uint64 {
 
 	default:
 		if _, ok := val.Index(0).Interface().(Hasher); !ok {
-			return nil
+			panic("slice elements must implement hrw.Hasher")
 		}
 
 		for i := 0; i < length; i++ {
@@ -293,9 +277,85 @@ func prepareRule(slice interface{}) []uint64 {
 // ValidateWeights checks if weights are normalized between 0.0 and 1.0
 func ValidateWeights(weights []float64) error {
 	for i := range weights {
-		if weights[i] > NormalizedMaxWeight || weights[i] < NormalizedMinWeight {
+		if math.IsNaN(weights[i]) || weights[i] > NormalizedMaxWeight || weights[i] < NormalizedMinWeight {
 			return errors.New("weights are not normalized")
 		}
 	}
 	return nil
 }
+
+// sortByWeight sorts nodes by weight using provided swapper.
+// nodes contains hrw hashes. If it is nil, indices are used.
+func sortByWeight(l int, byIndex bool, nodes []uint64, weights []float64, hash uint64, swap func(i, j int)) {
+	// if all nodes have the same distance then sort uniformly
+	if allSameF64(weights) {
+		sortByDistance(l, byIndex, nodes, hash, swap)
+		return
+	}
+
+	dist := make([]float64, l)
+	for i := 0; i < l; i++ {
+		d := getDistance(byIndex, i, nodes, hash)
+		// `maxUint64 - distance` makes the shorter distance more valuable
+		// it is necessary for operation with normalized values
+		dist[i] = float64(^uint64(0)-d) * weights[i]
+	}
+
+	s := &sorter{
+		l: l,
+		swap: func(i, j int) {
+			swap(i, j)
+			dist[i], dist[j] = dist[j], dist[i]
+		},
+		less: func(i, j int) bool {
+			return dist[i] > dist[j] // higher distance must be placed lower to be first
+		},
+	}
+	sort.Sort(s)
+}
+
+// sortByDistance sorts nodes by hrw distance using provided swapper.
+// nodes contains hrw hashes. If it is nil, indices are used.
+func sortByDistance(l int, byIndex bool, nodes []uint64, hash uint64, swap func(i, j int)) {
+	dist := make([]uint64, l)
+	for i := 0; i < l; i++ {
+		dist[i] = getDistance(byIndex, i, nodes, hash)
+	}
+
+	s := &sorter{
+		l: l,
+		swap: func(i, j int) {
+			swap(i, j)
+			dist[i], dist[j] = dist[j], dist[i]
+		},
+		less: func(i, j int) bool {
+			return dist[i] < dist[j]
+		},
+	}
+	sort.Sort(s)
+}
+
+// getDistance return distance from nodes[i] to h.
+// If byIndex is true, nodes index is used.
+// Else if nodes[i] != nil, distance is calculated from this value.
+// Otherwise, and hash from node index is taken.
+func getDistance(byIndex bool, i int, nodes []uint64, h uint64) uint64 {
+	if nodes != nil {
+		return distance(nodes[i], h)
+	} else if byIndex {
+		return distance(uint64(i), h)
+	} else {
+		buf := make([]byte, 8)
+		binary.LittleEndian.PutUint64(buf, uint64(i))
+		return distance(Hash(buf), h)
+	}
+}
+
+func allSameF64(fs []float64) bool {
+	for i := range fs {
+		if fs[i] != fs[0] {
+			return false
+		}
+	}
+	return true
+}

hrw_test.go

@@ -61,7 +61,7 @@ func Example() {
 }
 
 func (h hashString) Hash() uint64 {
-	return Hash([]byte(h))
+	return StringHash(string(h))
 }
 
 func TestSortSliceByIndex(t *testing.T) {
@@ -76,6 +76,9 @@ func TestValidateWeights(t *testing.T) {
 	weights := []float64{10, 10, 10, 2, 2, 2}
 	err := ValidateWeights(weights)
 	require.Error(t, err)
+	weights = []float64{math.NaN(), 1, 1, 0.2, 0.2, 0.2}
+	err = ValidateWeights(weights)
+	require.Error(t, err)
 	weights = []float64{1, 1, 1, 0.2, 0.2, 0.2}
 	err = ValidateWeights(weights)
 	require.NoError(t, err)
@@ -98,36 +101,6 @@ func TestSortSliceByValue(t *testing.T) {
 	require.Equal(t, expect, actual)
 }
 
-func TestSortByRule(t *testing.T) {
-	t.Run("direct", func(t *testing.T) {
-		//                  0    1    2    3    4    5
-		actual := []string{"a", "b", "c", "d", "e", "f"}
-		//                  4    2    0    5    3    1
-		expect := []string{"c", "f", "b", "e", "a", "d"}
-		rule := []uint64{4, 2, 0, 5, 3, 1}
-
-		sortByRuleDirect(
-			func(i, j int) { actual[i], actual[j] = actual[j], actual[i] },
-			6, rule)
-
-		require.Equal(t, expect, actual)
-	})
-
-	t.Run("inverse", func(t *testing.T) {
-		//                  0    1    2    3    4    5
-		actual := []string{"a", "b", "c", "d", "e", "f"}
-		//                  4    2    0    5    3    1
-		expect := []string{"e", "c", "a", "f", "d", "b"}
-		rule := []uint64{4, 2, 0, 5, 3, 1}
-
-		sortByRuleInverse(
-			func(i, j int) { actual[i], actual[j] = actual[j], actual[i] },
-			6, rule)
-
-		require.Equal(t, expect, actual)
-	})
-}
-
 func TestSortSliceByValueFail(t *testing.T) {
 	t.Run("empty slice", func(t *testing.T) {
 		var (
@@ -140,15 +113,13 @@ func TestSortSliceByValueFail(t *testing.T) {
 	t.Run("must be slice", func(t *testing.T) {
 		actual := 10
 		hash := Hash(testKey)
-		require.NotPanics(t, func() { SortSliceByValue(actual, hash) })
+		require.Panics(t, func() { SortSliceByValue(actual, hash) })
 	})
 
 	t.Run("must 'fail' for unknown type", func(t *testing.T) {
 		actual := []unknown{1, 2, 3, 4, 5}
-		expect := []unknown{1, 2, 3, 4, 5}
 		hash := Hash(testKey)
-		SortSliceByValue(actual, hash)
+		require.Panics(t, func() { SortSliceByValue(actual, hash) })
-		require.Equal(t, expect, actual)
 	})
 }
 
@@ -160,6 +131,23 @@ func TestSortSliceByValueHasher(t *testing.T) {
 	require.Equal(t, expect, actual)
 }
 
+func TestSortHasherSliceByValue(t *testing.T) {
+	actual := []hashString{"a", "b", "c", "d", "e", "f"}
+	expect := []hashString{"d", "f", "c", "b", "a", "e"}
+	hash := Hash(testKey)
+	SortHasherSliceByValue(actual, hash)
+	require.EqualValues(t, expect, actual)
+}
+
+func TestSortHasherSliceByWeightValue(t *testing.T) {
+	actual := []hashString{"a", "b", "c", "d", "e", "f"}
+	weights := []float64{1.0, 1.0, 1.0, 1.0, 1.0, 1.0}
+	expect := []hashString{"d", "f", "c", "b", "a", "e"}
+	hash := Hash(testKey)
+	SortHasherSliceByWeightValue(actual, weights, hash)
+	require.EqualValues(t, expect, actual)
+}
+
 func TestSortSliceByValueIntSlice(t *testing.T) {
 	cases := []slices{
 		{
@@ -202,11 +190,6 @@ func TestSortSliceByValueIntSlice(t *testing.T) {
 			expect: []uint32{5, 1, 2, 0, 3, 4},
 		},
 
-		{
-			actual: Uint32Slice{0, 1, 2, 3, 4, 5},
-			expect: Uint32Slice{0, 1, 2, 3, 4, 5},
-		},
-
 		{
 			actual: []int64{0, 1, 2, 3, 4, 5},
 			expect: []int64{5, 3, 0, 1, 4, 2},
@@ -670,6 +653,36 @@ func BenchmarkSortByValue_fnv_1000(b *testing.B) {
 	benchmarkSortByValue(b, 1000, hash)
 }
 
+func BenchmarkSortHashersByValue_Reflection_fnv_10(b *testing.B) {
+	hash := Hash(testKey)
+	benchmarkSortHashersByValueReflection(b, 10, hash)
+}
+
+func BenchmarkSortHashersByValue_Reflection_fnv_100(b *testing.B) {
+	hash := Hash(testKey)
+	benchmarkSortHashersByValueReflection(b, 100, hash)
+}
+
+func BenchmarkSortHashersByValue_Reflection_fnv_1000(b *testing.B) {
+	hash := Hash(testKey)
+	benchmarkSortHashersByValueReflection(b, 1000, hash)
+}
+
+func BenchmarkSortHashersByValue_Typed_fnv_10(b *testing.B) {
+	hash := Hash(testKey)
+	benchmarkSortHashersByValueTyped(b, 10, hash)
+}
+
+func BenchmarkSortHashersByValue_Typed_fnv_100(b *testing.B) {
+	hash := Hash(testKey)
+	benchmarkSortHashersByValueTyped(b, 100, hash)
+}
+
+func BenchmarkSortHashersByValue_Typed_fnv_1000(b *testing.B) {
+	hash := Hash(testKey)
+	benchmarkSortHashersByValueTyped(b, 1000, hash)
+}
+
 func BenchmarkSortByWeight_fnv_10(b *testing.B) {
 	hash := Hash(testKey)
 	_ = benchmarkSortByWeight(b, 10, hash)
@@ -715,6 +728,30 @@ func BenchmarkSortByWeightValue_fnv_1000(b *testing.B) {
 	benchmarkSortByWeightValue(b, 1000, hash)
 }
 
+func BenchmarkSortHashersByWeightValueReflection_fnv_10(b *testing.B) {
+	benchmarkSortHashersByWeightValueRelection(b, 10, Hash(testKey))
+}
+
+func BenchmarkSortHashersByWeightValueReflection_fnv_100(b *testing.B) {
+	benchmarkSortHashersByWeightValueRelection(b, 100, Hash(testKey))
+}
+
+func BenchmarkSortHashersByWeightValueReflection_fnv_1000(b *testing.B) {
+	benchmarkSortHashersByWeightValueRelection(b, 1000, Hash(testKey))
+}
+
+func BenchmarkSortHashersByWeightValueTyped_fnv_10(b *testing.B) {
+	benchmarkSortHashersByWeightValueTyped(b, 10, Hash(testKey))
+}
+
+func BenchmarkSortHashersByWeightValueTyped_fnv_100(b *testing.B) {
+	benchmarkSortHashersByWeightValueTyped(b, 100, Hash(testKey))
+}
+
+func BenchmarkSortHashersByWeightValueTyped_fnv_1000(b *testing.B) {
+	benchmarkSortHashersByWeightValueTyped(b, 1000, Hash(testKey))
+}
+
 func benchmarkSort(b *testing.B, n int, hash uint64) uint64 {
 	servers := make([]uint64, n)
 	for i := uint64(0); i < uint64(len(servers)); i++ {
@@ -808,3 +845,63 @@ func benchmarkSortByWeightValue(b *testing.B, n int, hash uint64) {
 		SortSliceByWeightValue(servers, weights, hash)
 	}
 }
+
+func benchmarkSortHashersByWeightValueRelection(b *testing.B, n int, hash uint64) {
+	servers := make([]hashString, n)
+	weights := make([]float64, n)
+	for i := uint64(0); i < uint64(len(servers)); i++ {
+		weights[i] = float64(uint64(n)-i) / float64(n)
+		servers[i] = hashString("localhost:" + strconv.FormatUint(60000-i, 10))
+	}
+
+	b.ResetTimer()
+	b.ReportAllocs()
+
+	for i := 0; i < b.N; i++ {
+		SortSliceByWeightValue(servers, weights, hash)
+	}
+}
+
+func benchmarkSortHashersByWeightValueTyped(b *testing.B, n int, hash uint64) {
+	servers := make([]hashString, n)
+	weights := make([]float64, n)
+	for i := uint64(0); i < uint64(len(servers)); i++ {
+		weights[i] = float64(uint64(n)-i) / float64(n)
+		servers[i] = hashString("localhost:" + strconv.FormatUint(60000-i, 10))
+	}
+
+	b.ResetTimer()
+	b.ReportAllocs()
+
+	for i := 0; i < b.N; i++ {
+		SortHasherSliceByWeightValue(servers, weights, hash)
+	}
+}
+
+func benchmarkSortHashersByValueReflection(b *testing.B, n int, hash uint64) {
+	servers := make([]hashString, n)
+	for i := uint64(0); i < uint64(len(servers)); i++ {
+		servers[i] = hashString("localhost:" + strconv.FormatUint(60000-i, 10))
+	}
+
+	b.ResetTimer()
+	b.ReportAllocs()
+
+	for i := 0; i < b.N; i++ {
+		SortSliceByValue(servers, hash)
+	}
+}
+
+func benchmarkSortHashersByValueTyped(b *testing.B, n int, hash uint64) {
+	servers := make([]hashString, n)
+	for i := uint64(0); i < uint64(len(servers)); i++ {
+		servers[i] = hashString("localhost:" + strconv.FormatUint(60000-i, 10))
+	}
+
+	b.ResetTimer()
+	b.ReportAllocs()
+
+	for i := 0; i < b.N; i++ {
+		SortHasherSliceByValue(servers, hash)
+	}
+}