go-hackers-delight

An interactive Go showcase of "Hacker's Delight" 2nd Edition by Henrey S.Warren Jr, 2013.¹²

If you write optimizing compilers or high-performance code, you must read this book. — Guy L. Steele [PhD, ACM Award, AAAI Fellow, Sun Fellow, core Java design]

This is the first book that promises to tell the deep, dark secrets of computer arithmetic, and it delivers in spades. It contains every trick I knew plus many, many more. A godsend for library developers, compiler writers, and lovers of elegant hacks. It deserves a spot on your self right next to Knuth. In the ten years since the first edition came out, it's been absolutely invaluable to my work at Sun and Google. — Joshua Bloch [PhD, Distinguished Engineer at Sun, Chief Java Architect at Google 2004~2012]

Methodology

extensively fuzzing
not using any Go packages, not even standard library
using generics whenever possible
verifying compiled code via https://godbolt.org

Observations

native Abs performance is the same
native Div and Mod by small constants performance is better
native math/bits.Mul32 and math/bits.Mul64³ performance is the same
native math/bits.LeadingZeros performance is better than LeadingZeroes algorithm
native math.Sqrt performance is better
native math.Pow(x, 1./3)⁴ performance is worse than Cbrt algorithm 💥
native math.Pow(x, 1./3)⁴⁵ underflows but Cbrt algorithm is correct 💥
native math.Pow(x, n)⁴ performance is worse than Pow algorithm 💥
native math.Log2(x)⁴ performance is worse than Log2 algorithm 💥
native math.Log10(x)⁴ performance is worse than Log10 algorithm 💥
native math.Log10(x) ⁴⁵ overflows for math.MaxUint64 but Log10 algorithm is correct 💥
native 1/math.Sqrt(x) performance is 1.5x better than RSqrtFloat32 algorithm
native switch performance is better than CycleThreeValues algorithm
native crc32.Checksum performance is 30x~500x better than CRC32 algorithms
simplistic LRUCache performance is 3x worse than LRUCache algorithm 💥

Appendix: Benchmarks

$ go test -bench .
goos: darwin
goarch: arm64
pkg: github.com/nikolaydubina/go-hackers-delight
BenchmarkNoop/---------------------------------16         	1000000000	         0.0000001 ns/op
BenchmarkAbs/basic-16                                     	1000000000	         0.9826 ns/op
BenchmarkAbs/Abs-16                                       	1000000000	         0.9647 ns/op
BenchmarkAbs/Abs2-16                                      	1000000000	         0.9943 ns/op
BenchmarkAbs/Abs3-16                                      	1000000000	         0.9819 ns/op
BenchmarkAbs/Abs4-16                                      	1000000000	         1.003 ns/op
BenchmarkAbs/AbsFastMul-16                                	1000000000	         0.9598 ns/op
BenchmarkAvg/basic-16                                     	973716225	         2.045 ns/op
BenchmarkAvg/AvgFloor-16                                  	602586224	         2.050 ns/op
BenchmarkAvg/AvgCeil-16                                   	582029594	         2.054 ns/op
BenchmarkCycleThree/basic-16                              	767160418	         1.560 ns/op
BenchmarkCycleThree/CycleThreeValues-16                   	438818894	         2.729 ns/op
BenchmarkLeadingZeros/uint32/basic-16                     	1000000000	         0.9419 ns/op
BenchmarkLeadingZeros/uint32/LeadingZerosUint32-16        	1000000000	         1.124 ns/op
BenchmarkLeadingZeros/uint64/basic-16                     	1000000000	         0.9230 ns/op
BenchmarkLeadingZeros/uint64/LeadingZerosUint64-16        	898095195	         1.336 ns/op
BenchmarkCompress/Compress-16                             	100000000	        10.60 ns/op
BenchmarkCompress/Compress2-16                            	55584826	        21.52 ns/op
BenchmarkLRU/basic-16                                     	246358870	         4.870 ns/op
BenchmarkLRU/LRUCache-16                                  	960896830	         1.239 ns/op
BenchmarkMul/uint32/basic-16                              	593555838	         1.892 ns/op
BenchmarkMul/uint32/MultiplyHighOrder32-16                	951445552	         2.046 ns/op
BenchmarkMul/uint64/basic-16                              	977065424	         1.220 ns/op
BenchmarkMul/uint64/MultiplyHighOrder64-16                	675693746	         2.042 ns/op
BenchmarkDivMod/DivMod/3/basic-16                         	1000000000	         0.8500 ns/op
BenchmarkDivMod/DivMod/3/DivMod3Signed-16                 	605588445	         1.970 ns/op
BenchmarkDivMod/DivMod/3/DivMod3Signed2-16                	1000000000	         1.078 ns/op
BenchmarkDivMod/DivMod/7/basic-16                         	1000000000	         0.8311 ns/op
BenchmarkDivMod/DivMod/7/DivMod7Signed-16                 	582087586	         2.105 ns/op
BenchmarkDivMod/Div/3/basic-16                            	1000000000	         0.8325 ns/op
BenchmarkDivMod/Div/3/Div3Signed-16                       	793883130	         1.509 ns/op
BenchmarkDivMod/Div/3/Div3ShiftSigned-16                  	907116610	         1.320 ns/op
BenchmarkDivMod/Div/7/basic-16                            	1000000000	         0.8344 ns/op
BenchmarkDivMod/Div/7/Div7Signed-16                       	755509315	         1.590 ns/op
BenchmarkDivMod/Div/7/Div7ShiftSigned-16                  	841563656	         1.424 ns/op
BenchmarkDivMod/Mod/3/basic-16                            	1000000000	         0.8309 ns/op
BenchmarkDivMod/Mod/3/Mod3Signed-16                       	812136249	         1.466 ns/op
BenchmarkDivMod/Mod/3/Mod3Signed2-16                      	1000000000	         0.8410 ns/op
BenchmarkDivMod/Mod/7/basic-16                            	1000000000	         0.8332 ns/op
BenchmarkDivMod/Mod/7/Mod7Signed-16                       	766677633	         1.564 ns/op
BenchmarkDivMod/Mod/7/Mod7Signed2-16                      	1000000000	         1.095 ns/op
BenchmarkDivMod/Mod/10/basic-16                           	1000000000	         0.8318 ns/op
BenchmarkDivMod/Mod/10/Mod10Signed-16                     	868932930	         1.441 ns/op
BenchmarkDivMod/DivExact/7/basic-16                       	1000000000	         0.9247 ns/op
BenchmarkDivMod/DivExact/7/DivExact7-16                   	1000000000	         0.9238 ns/op
BenchmarkDivMod/DivExact/7/Div7Signed-16                  	718667949	         1.668 ns/op
BenchmarkDivMod/DivExact/7/Div7ShiftSigned-16             	802988229	         1.490 ns/op
BenchmarkCbrt/basic-16                                    	47340079	        26.01 ns/op
BenchmarkCbrt/Cbrt-16                                     	85196262	        14.55 ns/op
BenchmarkPow/basic-16                                     	24005180	        48.25 ns/op
BenchmarkPow/Pow-16                                       	65121390	        19.08 ns/op
BenchmarkLog/uint32/2/basic-16                            	99810775	        12.06 ns/op
BenchmarkLog/uint32/2/Log2-16                             	984283590	         1.223 ns/op
BenchmarkLog/uint32/10/basic-16                           	140540709	         8.516 ns/op
BenchmarkLog/uint32/10/Log10-16                           	539441811	         2.220 ns/op
BenchmarkLog/uint64/2/basic-16                            	100000000	        11.73 ns/op
BenchmarkLog/uint64/2/Log2-16                             	839779903	         1.419 ns/op
BenchmarkLog/uint64/10/basic-16                           	142679388	         8.419 ns/op
BenchmarkLog/uint64/10/Log10-16                           	538269764	         2.228 ns/op
BenchmarkSqrt/basic-16                                    	1000000000	         1.019 ns/op
BenchmarkSqrt/SqrtNewton-16                               	188142513	         6.538 ns/op
BenchmarkSqrt/SqrtBinarySearch-16                         	74752382	        15.71 ns/op
BenchmarkSqrt/SqrtShiftAndSubtract-16                     	136426688	         8.834 ns/op
BenchmarkCRC32/basic-16                                   	220094371	         5.395 ns/op
BenchmarkCRC32/CRC32Basic-16                              	  448540	      2510 ns/op
BenchmarkCRC32/CRC32TableLookup-16                        	 8108901	       147.5 ns/op
BenchmarkRSqrtFloat32/basic-16                            	1000000000	         0.9354 ns/op
BenchmarkRSqrtFloat32/RSqrtFloat32-16                     	828149971	         1.448 ns/op
PASS
ok  	github.com/nikolaydubina/go-hackers-delight	91.183s

showcase in C — https://github.com/hcs0/Hackers-Delight ↩
showcase in Rust — https://github.com/victoryang00/Delight ↩
given manual inlining of generic type, which produces equivalent Go code ↩
we are comparing native float64 result converted to uint32, as there is no better standard function ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶
which is due to float64 not having enough precision ↩ ↩²

Name		Name	Last commit message	Last commit date
Latest commit History 233 Commits
.github		.github
testdata/fuzz		testdata/fuzz
00_bit_packing.go		00_bit_packing.go
00_bit_packing_test.go		00_bit_packing_test.go
00_constants.go		00_constants.go
00_constants_test.go		00_constants_test.go
00_shift.go		00_shift.go
00_test.go		00_test.go
00_types.go		00_types.go
02-00.go		02-00.go
02-01_demorgan_laws_extended_test.go		02-01_demorgan_laws_extended_test.go
02-01_manipulating_rightmost_bits.go		02-01_manipulating_rightmost_bits.go
02-01_manipulating_rightmost_bits_test.go		02-01_manipulating_rightmost_bits_test.go
02-01_next_higher_number_with_same_num_ones.go		02-01_next_higher_number_with_same_num_ones.go
02-01_next_higher_number_with_same_num_ones_test.go		02-01_next_higher_number_with_same_num_ones_test.go
02-02_logic_operations_with_addition_test.go		02-02_logic_operations_with_addition_test.go
02-03_inequalitties_among_logic_and_arithmetic_test.go		02-03_inequalitties_among_logic_and_arithmetic_test.go
02-04_abs.go		02-04_abs.go
02-04_abs_test.go		02-04_abs_test.go
02-05_avg.go		02-05_avg.go
02-05_avg_test.go		02-05_avg_test.go
02-06_sign.go		02-06_sign.go
02-06_sign_test.go		02-06_sign_test.go
02-11_zero_means_2_to_n_test.go		02-11_zero_means_2_to_n_test.go
02-12_comparison.go		02-12_comparison.go
02-12_comparison_test.go		02-12_comparison_test.go
02-13_overflow.go		02-13_overflow.go
02-13_overflow_test.go		02-13_overflow_test.go
02-15_rotate_shifts.go		02-15_rotate_shifts.go
02-15_rotate_shifts_test.go		02-15_rotate_shifts_test.go
02-16_double_length_add_sub.go		02-16_double_length_add_sub.go
02-16_double_length_add_sub_test.go		02-16_double_length_add_sub_test.go
02-17_double_length_shifts.go		02-17_double_length_shifts.go
02-17_double_length_shifts_test.go		02-17_double_length_shifts_test.go
02-18_multibyte_arithmetics.go		02-18_multibyte_arithmetics.go
02-18_multibyte_arithmetics_test.go		02-18_multibyte_arithmetics_test.go
02-19_doz_max_min.go		02-19_doz_max_min.go
02-19_doz_max_min_test.go		02-19_doz_max_min_test.go
02-20_exchanging_registers.go		02-20_exchanging_registers.go
02-20_exchanging_registers_test.go		02-20_exchanging_registers_test.go
02-21_alternating_values.go		02-21_alternating_values.go
02-21_alternating_values_test.go		02-21_alternating_values_test.go
03-00_power_of_two_boundaries.go		03-00_power_of_two_boundaries.go
03-00_power_of_two_boundaries_test.go		03-00_power_of_two_boundaries_test.go
04-00_arithmetic_bounds.go		04-00_arithmetic_bounds.go
04-00_arithmetic_bounds_test.go		04-00_arithmetic_bounds_test.go
04-03_arithmetic_bounds_propagating_logical.go		04-03_arithmetic_bounds_propagating_logical.go
04-03_arithmetic_bounds_propagating_logical_test.go		04-03_arithmetic_bounds_propagating_logical_test.go
05-01_counting_ones.go		05-01_counting_ones.go
05-01_counting_ones_test.go		05-01_counting_ones_test.go
05-02_parity.go		05-02_parity.go
05-02_parity_test.go		05-02_parity_test.go
05-03_counting_zeros.go		05-03_counting_zeros.go
05-03_counting_zeros_test.go		05-03_counting_zeros_test.go
06-00_searching_words.go		06-00_searching_words.go
06-00_searching_words_test.go		06-00_searching_words_test.go
07-01_reversing_bits_and_bytes.go		07-01_reversing_bits_and_bytes.go
07-01_reversing_bits_and_bytes_test.go		07-01_reversing_bits_and_bytes_test.go
07-02_shuffle.go		07-02_shuffle.go
07-02_shuffle_test.go		07-02_shuffle_test.go
07-03_transposing_bit_matrix.go		07-03_transposing_bit_matrix.go
07-03_transposing_bit_matrix_test.go		07-03_transposing_bit_matrix_test.go
07-04_compress.go		07-04_compress.go
07-04_compress_test.go		07-04_compress_test.go
07-09_lru.go		07-09_lru.go
07-09_lru_test.go		07-09_lru_test.go
08-00_multiplication.go		08-00_multiplication.go
08-00_multiplication_test.go		08-00_multiplication_test.go
09-00_integer_division.go		09-00_integer_division.go
09-00_integer_division_test.go		09-00_integer_division_test.go
10-00_integer_division_by_constant.go		10-00_integer_division_by_constant.go
10-00_integer_division_by_constant_test.go		10-00_integer_division_by_constant_test.go
10-01_integer_division_by_constant_signed.go		10-01_integer_division_by_constant_signed.go
10-01_integer_division_by_constant_signed_test.go		10-01_integer_division_by_constant_signed_test.go
10-08_integer_division_by_constant_unsigned.go		10-08_integer_division_by_constant_unsigned.go
10-08_integer_division_by_constant_unsigned_test.go		10-08_integer_division_by_constant_unsigned_test.go
10-16_integer_division_by_constant_exact.go		10-16_integer_division_by_constant_exact.go
10-16_integer_division_by_constant_exact_test.go		10-16_integer_division_by_constant_exact_test.go
10-17_integer_division_by_constant_shifts.go		10-17_integer_division_by_constant_shifts.go
10-17_integer_division_by_constant_shifts_test.go		10-17_integer_division_by_constant_shifts_test.go
10-19_integer_division_by_constant_reminder.go		10-19_integer_division_by_constant_reminder.go
10-19_integer_division_by_constant_reminder_test.go		10-19_integer_division_by_constant_reminder_test.go
11-00_elementary_functions.go		11-00_elementary_functions.go
11-00_elementary_functions_test.go		11-00_elementary_functions_test.go
11-01_sqrt.go		11-01_sqrt.go
11-01_sqrt_test.go		11-01_sqrt_test.go
12-00_unusual_bases_number_systems.go		12-00_unusual_bases_number_systems.go
13-00_gray_code.go		13-00_gray_code.go
13-00_gray_code_test.go		13-00_gray_code_test.go
14-00_cyclic_redundancy_check.go		14-00_cyclic_redundancy_check.go
14-00_cyclic_redundancy_check_test.go		14-00_cyclic_redundancy_check_test.go
15-00_error_correcting_codes.go		15-00_error_correcting_codes.go
15-00_error_correcting_codes_test.go		15-00_error_correcting_codes_test.go
17-00_floating_point.go		17-00_floating_point.go
17-00_floating_point_test.go		17-00_floating_point_test.go
18-00_primes.go		18-00_primes.go
LICENSE		LICENSE
README.md		README.md
go.mod		go.mod

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Repository files navigation

go-hackers-delight

Methodology

Observations

About

Releases 2

Sponsor this project

Languages

License

nikolaydubina/go-hackers-delight

Folders and files

Latest commit

History

Repository files navigation

go-hackers-delight

Methodology

Observations

Footnotes

About

Topics

Resources

License

Stars

Watchers

Forks

Releases 2

Sponsor this project

Languages