Created
May 19, 2018 17:08
-
-
Save dt-rush/6694b0b205f23d2a2e4afd6a1c6f72f2 to your computer and use it in GitHub Desktop.
[go] Demonstrating that indexing a map[uint32] takes longer with larger indexes
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* This was written to show that indexing a map with numbers | |
| * formed by putting two uint16's into a single uint32 takes longer | |
| * than indexing a map with uint16's in the range [0, 1023] | |
| */ | |
| package main | |
| import ( | |
| "fmt" | |
| "time" | |
| "math/rand" | |
| ) | |
| // used to iterate a lot of times | |
| const N = 1024 | |
| // something to put in the map | |
| type ExampleStruct struct { | |
| c chan(bool) | |
| } | |
| // a type representing a function which, given two uint16's, will return | |
| // a uint32 index | |
| type IndexFunc func (i uint16, j uint16) uint32 | |
| // iterate (N * (N-1)) / 2 times (that is, produce every pairing of numbers | |
| // from 0 to N-1), and use the supplied IndexFunc to put an ExampleStruct | |
| // into a map. return the milliseconds taken to do this | |
| func doMapping(index IndexFunc, name string) int64 { | |
| t0 := time.Now().UnixNano() | |
| m := make(map[uint32]ExampleStruct) | |
| for i := 0; i < N; i++ { | |
| for j := i + 1; j < N; j++ { | |
| // compute the index given the IndexFunc and store an object | |
| // in the map | |
| ix := index(uint16(i), uint16(j)) | |
| m[ix] = ExampleStruct{make(chan(bool))} | |
| // once in a while report a representative index to the console | |
| if rand.Intn(1e6) == 0 { | |
| fmt.Printf ("representative index for %s(%d,%d): %d\n", | |
| name, i, j, ix) | |
| } | |
| } | |
| } | |
| t1 := time.Now().UnixNano() | |
| return (t1 - t0) / 1e6 | |
| } | |
| // the number of times to run each call to doMapping() in profile() | |
| const N_TIMES = 24 | |
| // call doMapping a certain number of times with the supplied IndexFunc | |
| // and calculate the average time taken | |
| func profile( | |
| indexFunc IndexFunc, | |
| indexFuncStr string, | |
| name string) { | |
| durations := [N_TIMES]int64{} | |
| for i := 0; i < N_TIMES; i++ { | |
| durations[i] = doMapping(indexFunc, name) | |
| } | |
| // calculate and report the average | |
| sum := int64(0) | |
| for i := 0; i < N_TIMES; i++ { | |
| sum += durations[i] | |
| } | |
| fmt.Println() | |
| fmt.Printf("avg time for `%s`: %d ms\n", indexFuncStr, sum / N_TIMES) | |
| fmt.Println() | |
| } | |
| func main () { | |
| rand.Seed(time.Now().UnixNano()) | |
| // run the test with low indexes | |
| profile(func (i uint16, j uint16) uint32 { | |
| return uint32(i * N + j) | |
| }, | |
| "i * N + j", | |
| "lowIndexes") | |
| // run the test with high indexes | |
| profile(func (i uint16, j uint16) uint32 { | |
| return uint32(i) << 16 | uint32(j) | |
| }, | |
| "i << 16 | j", | |
| "highIndexes") | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment