tune.odin 4.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159
  1. /*
  2. Copyright 2021 Jeroen van Rijn <[email protected]>.
  3. Made available under Odin's BSD-3 license.
  4. A BigInt implementation in Odin.
  5. For the theoretical underpinnings, see Knuth's The Art of Computer Programming, Volume 2, section 4.3.
  6. The code started out as an idiomatic source port of libTomMath, which is in the public domain, with thanks.
  7. */
  8. #+build ignore
  9. package math_big
  10. import "core:time"
  11. import "base:runtime"
  12. print_value :: proc(name: string, value: i64) {
  13. runtime.print_string("\t")
  14. runtime.print_string(name)
  15. runtime.print_string(": ")
  16. runtime.print_i64(value)
  17. runtime.print_string("\n")
  18. }
  19. print_bool :: proc(name: string, value: bool) {
  20. runtime.print_string("\t")
  21. runtime.print_string(name)
  22. if value {
  23. runtime.print_string(": true\n")
  24. } else {
  25. runtime.print_string(": false\n")
  26. }
  27. }
  28. print_configation :: proc() {
  29. runtime.print_string("Configuration:\n")
  30. print_value("_DIGIT_BITS ", _DIGIT_BITS)
  31. print_bool ("MATH_BIG_SMALL_MEMORY ", _LOW_MEMORY)
  32. print_value("_MIN_DIGIT_COUNT ", _MIN_DIGIT_COUNT)
  33. print_value("_MAX_DIGIT_COUNT ", i64(_MAX_DIGIT_COUNT))
  34. print_value("_DEFAULT_DIGIT_COUNT ", _DEFAULT_DIGIT_COUNT)
  35. print_value("_MAX_COMBA ", _MAX_COMBA)
  36. print_value("_WARRAY ", _WARRAY)
  37. print_value("_TAB_SIZE ", _TAB_SIZE)
  38. print_value("_MAX_WIN_SIZE ", _MAX_WIN_SIZE)
  39. print_bool ("MATH_BIG_USE_LUCAS_SELFRIDGE_TEST ", MATH_BIG_USE_LUCAS_SELFRIDGE_TEST)
  40. runtime.print_string("\nRuntime tunable:\n")
  41. print_value("MUL_KARATSUBA_CUTOFF ", i64(MUL_KARATSUBA_CUTOFF))
  42. print_value("SQR_KARATSUBA_CUTOFF ", i64(SQR_KARATSUBA_CUTOFF))
  43. print_value("MUL_TOOM_CUTOFF ", i64(MUL_TOOM_CUTOFF))
  44. print_value("SQR_TOOM_CUTOFF ", i64(SQR_TOOM_CUTOFF))
  45. print_value("MAX_ITERATIONS_ROOT_N ", i64(MAX_ITERATIONS_ROOT_N))
  46. print_value("FACTORIAL_MAX_N ", i64(FACTORIAL_MAX_N))
  47. print_value("FACTORIAL_BINARY_SPLIT_CUTOFF ", i64(FACTORIAL_BINARY_SPLIT_CUTOFF))
  48. print_value("FACTORIAL_BINARY_SPLIT_MAX_RECURSIONS", i64(FACTORIAL_BINARY_SPLIT_MAX_RECURSIONS))
  49. print_value("FACTORIAL_BINARY_SPLIT_CUTOFF ", i64(FACTORIAL_BINARY_SPLIT_CUTOFF))
  50. print_bool ("USE_MILLER_RABIN_ONLY ", USE_MILLER_RABIN_ONLY)
  51. print_value("MAX_ITERATIONS_RANDOM_PRIME ", i64(MAX_ITERATIONS_RANDOM_PRIME))
  52. }
  53. print :: proc(name: string, a: ^Int, base := i8(10), print_name := true, newline := true, print_extra_info := false) {
  54. assert_if_nil(a)
  55. as, err := itoa(a, base)
  56. defer delete(as)
  57. cb := internal_count_bits(a)
  58. if print_name {
  59. runtime.print_string(name)
  60. }
  61. if err != nil {
  62. runtime.print_string("(Error: ")
  63. es := Error_String
  64. runtime.print_string(es[err])
  65. runtime.print_string(")")
  66. }
  67. runtime.print_string(as)
  68. if print_extra_info {
  69. runtime.print_string(" (base: ")
  70. runtime.print_i64(i64(base))
  71. runtime.print_string(", bits: ")
  72. runtime.print_i64(i64(cb))
  73. runtime.print_string(", digits: ")
  74. runtime.print_i64(i64(a.used))
  75. runtime.print_string(")")
  76. }
  77. if newline {
  78. runtime.print_string("\n")
  79. }
  80. }
  81. Category :: enum {
  82. itoa,
  83. atoi,
  84. factorial,
  85. factorial_bin,
  86. choose,
  87. lsb,
  88. ctz,
  89. sqr,
  90. bitfield_extract,
  91. rm_trials,
  92. is_prime,
  93. random_prime,
  94. }
  95. Event :: struct {
  96. ticks: time.Duration,
  97. count: int,
  98. cycles: u64,
  99. }
  100. Timings := [Category]Event{}
  101. print_timings :: proc() {
  102. // duration :: proc(d: time.Duration) -> (res: string) {
  103. // switch {
  104. // case d < time.Microsecond:
  105. // return fmt.tprintf("%v ns", time.duration_nanoseconds(d))
  106. // case d < time.Millisecond:
  107. // return fmt.tprintf("%v µs", time.duration_microseconds(d))
  108. // case:
  109. // return fmt.tprintf("%v ms", time.duration_milliseconds(d))
  110. // }
  111. // }
  112. // for v in Timings {
  113. // if v.count > 0 {
  114. // fmt.println("\nTimings:")
  115. // break
  116. // }
  117. // }
  118. // for v, i in Timings {
  119. // if v.count > 0 {
  120. // avg_ticks := time.Duration(f64(v.ticks) / f64(v.count))
  121. // avg_cycles := f64(v.cycles) / f64(v.count)
  122. // fmt.printf("\t%v: %s / %v cycles (avg), %s / %v cycles (total, %v calls)\n", i, duration(avg_ticks), avg_cycles, duration(v.ticks), v.cycles, v.count)
  123. // }
  124. // }
  125. }
  126. @(deferred_in_out=_SCOPE_END)
  127. SCOPED_TIMING :: #force_inline proc(c: Category) -> (ticks: time.Tick, cycles: u64) {
  128. cycles = time.read_cycle_counter()
  129. ticks = time.tick_now()
  130. return
  131. }
  132. _SCOPE_END :: #force_inline proc(c: Category, ticks: time.Tick, cycles: u64) {
  133. cycles_now := time.read_cycle_counter()
  134. ticks_now := time.tick_now()
  135. Timings[c].ticks = time.tick_diff(ticks, ticks_now)
  136. Timings[c].cycles = cycles_now - cycles
  137. Timings[c].count += 1
  138. }
  139. SCOPED_COUNT_ADD :: #force_inline proc(c: Category, count: int) {
  140. Timings[c].count += count
  141. }