mirror of
https://github.com/nim-lang/Nim.git
synced 2025-12-29 01:14:41 +00:00
8088633250
* ttables: smaller table, 5x speedup * thavlak: less iterations, less loops; 30% speedup * tasyncclosestall: shorter timeout; 35% speedup * gcleak4: less iterations, 2x speedup * ttimes: remove deprecated stuff * tdangerisrelease: remove cpp backend, 3x speedup * tfrexp1: smaller range, 2x speedup * trtree: fix warnings, less iterations, 6x speedup * tasyncawait_cyclebreaker: smaller swarm size; 2x speedup * trealloc: smaller number of iterations; 10x speedup * towned_binary_tree: less iterations, 4x speedup * tclosure: remove unused code, less iterations; 2x speedup * twaitany: less durations; 1.4x speedup * tasync_misc: less iterations, 2x speedup * t8535: smaller sleep, 1.5x speedup * tmanyjoin: smaller sleep, 2x speedup * t12221: shorter sleeps, removed two slower tests; 1.6x speedup * tfuturestream: smaller sleep; 1.5x speedup * growobjcrash: less iterations; 2x speedup * ttryrecv: smaller sleep; 1.5x speedup * treusetvar: less threads; 2x speedup * delete tthreadanalysis2, basically a duplicate of tthreadanalysis * t7758: less iterations, 1.5x speedup * tasyncawait: smaller swarm, less messages; 1.5x speedup * tjsandnativeasync: smaller sleep, 1.5x speedup * tpendingcheck: smaller sleep, 1.5x speedup * remove rodfiles test category * move tseq from its own category to 'collections' category * remove unneeded tests and helpers from 'assert' category * stdlib: merge tbitops2 into tbitops * remove 'trepr2' from 'stdlib' cat * merge 'tstreams' into one file * remove 'tinefficient_const_table' from 'ccbugs' cat * merge 'tcollections_to_string' into 'tcollections' * tblocking_channel: smaller sleep, small speedup * tconvexhull: less iterartions; 1.2x speedup * merge 'tdeepcopy2' into 'tdeepcopy' * merge 'tdisjoint_slice2' into 'tdisjoint_slice1' * tmissing_deepcopy: smaller sequence * tsendtwice: smaller arrays; 5x speedup * remove 'tindexerrorformatbounds' * disable multimethod tests * remove 'gc:none' and 'refc' without 'd:useRealtimeGC' from gc tests * koch.nim: bootstrap just with '-d:release', no need for 'csource' * add github workflow for documentation * testament: no need for 8 sub-second decimals
92 lines
2.2 KiB
Nim
92 lines
2.2 KiB
Nim
discard """
|
|
cmd: '''nim c -d:nimAllocStats --newruntime $file'''
|
|
output: '''31665
|
|
(allocCount: 33335, deallocCount: 33335)'''
|
|
"""
|
|
|
|
# bug #11053
|
|
|
|
import random
|
|
|
|
type Node = ref object
|
|
x, y: int32
|
|
left, right: owned Node
|
|
|
|
proc newNode(x: int32): owned Node =
|
|
result = Node(x: x, y: rand(high int32).int32)
|
|
|
|
proc merge(lower, greater: owned Node): owned Node =
|
|
if lower.isNil:
|
|
result = greater
|
|
elif greater.isNil:
|
|
result = lower
|
|
elif lower.y < greater.y:
|
|
lower.right = merge(lower.right, greater)
|
|
result = lower
|
|
else:
|
|
greater.left = merge(lower, greater.left)
|
|
result = greater
|
|
|
|
proc splitBinary(orig: owned Node, value: int32): (owned Node, owned Node) =
|
|
if orig.isNil:
|
|
result = (nil, nil)
|
|
elif orig.x < value:
|
|
let splitPair = splitBinary(orig.right, value)
|
|
orig.right = splitPair[0]
|
|
result = (orig, splitPair[1])
|
|
else:
|
|
let splitPair = splitBinary(orig.left, value)
|
|
orig.left = splitPair[1]
|
|
result = (splitPair[0], orig)
|
|
|
|
proc merge3(lower, equal, greater: owned Node): owned Node =
|
|
merge(merge(lower, equal), greater)
|
|
|
|
proc split(orig: owned Node, value: int32): tuple[lower, equal, greater: owned Node] =
|
|
let
|
|
(lower, equalGreater) = splitBinary(orig, value)
|
|
(equal, greater) = splitBinary(equalGreater, value + 1)
|
|
result = (lower, equal, greater)
|
|
|
|
type Tree = object
|
|
root: owned Node
|
|
|
|
proc hasValue(self: var Tree, x: int32): bool =
|
|
let splited = split(move self.root, x)
|
|
result = not splited.equal.isNil
|
|
self.root = merge3(splited.lower, splited.equal, splited.greater)
|
|
|
|
proc insert(self: var Tree, x: int32) =
|
|
var splited = split(move self.root, x)
|
|
if splited.equal.isNil:
|
|
splited.equal = newNode(x)
|
|
self.root = merge3(splited.lower, splited.equal, splited.greater)
|
|
|
|
proc erase(self: var Tree, x: int32) =
|
|
let splited = split(move self.root, x)
|
|
self.root = merge(splited.lower, splited.greater)
|
|
|
|
proc main() =
|
|
var
|
|
tree = Tree()
|
|
cur = 5'i32
|
|
res = 0
|
|
|
|
for i in 1 ..< 100000:
|
|
let a = i mod 3
|
|
cur = (cur * 57 + 43) mod 10007
|
|
case a:
|
|
of 0:
|
|
tree.insert(cur)
|
|
of 1:
|
|
tree.erase(cur)
|
|
of 2:
|
|
if tree.hasValue(cur):
|
|
res += 1
|
|
else:
|
|
discard
|
|
echo res
|
|
|
|
dumpAllocStats:
|
|
main()
|