blob: ec5c5ba4e3444b601e3ede55a1a6ce3d202c4426 [file] [edit]
// Copyright 2026 The Dawn & Tint Authors
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// 1. Redistributions of source code must retain the above copyright notice, this
// list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright notice,
// this list of conditions and the following disclaimer in the documentation
// and/or other materials provided with the distribution.
//
// 3. Neither the name of the copyright holder nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
package node
import (
"dawn.googlesource.com/dawn/tools/src/cmd/run-cts/common"
)
// shardOf returns the shard, out of m shards, of the test case at position k of
// the listed test cases.
//
// CTS test cases can fall into patterns of longer and shorter running cases.
// To make it unlikely that one shard gets a disproportionate share of the long
// running cases, map a test index to a shard index via a hash function that
// deals well with inputs that form an arithmetic sequence. A Fibonacci hash
// function works particularly well. See Knuth, The Art of Computer Programming,
// Vol. 3, Section 6.4, for intuition and details.
//
// Consider standard multiplicative hashing, mapping an integer k into the range
// {0,...,m-1}. Choose W larger than m, and 'a' relatively prime to W. Then the
// standard multiplicative hash function is:
//
// h_a(k) = floor( ((a * k) mod W ) / (W / m) )
// = floor( ((a * k) mod W ) * (m / W) )
//
// We simplify the math involving W by choosing W to be (1<<32). Then the
// 'mod W' is computed with wrapping arithmetic in uint32, and the division by W
// is computed as a right shift starting with a 64-bit result.
//
// With Fibonacci hashing, choose 'a' to be the odd number closest to W/phi
// where phi is the golden ratio 1.618...
//
// We therefore have pseudo-code:
//
// const uint32 a = W / phi;
//
// h_a(k) = ( uint64(uint32(a * k)) * uint64(m) ) >> 32;
func shardOf(k, m int) int {
const a = 0x9E3779B9 // The odd number closest to W/phi.
return int((uint64(uint32(k)*a) * uint64(m)) >> 32)
}
// shardCases returns the test cases of shard index out of count, in the order
// they were listed.
func shardCases(cases []common.TestCase, index, count int) []common.TestCase {
shard := []common.TestCase{}
for k, testCase := range cases {
if shardOf(k, count) == index {
shard = append(shard, testCase)
}
}
return shard
}