Details
-
Sub-task
-
Status: Closed
-
Major
-
Resolution: Fixed
-
None
-
None
Description
Too much time can be spent in Application.sortRequests(). There are various ways to solve this problem.
Two competing approaches:
- Store requests in a sorted data structures (btree.BTree from Google)
- Only sort if a new request is added. If pendingAskRepeat becomes 0, simply skip it.
Based on benchmarks, #2 is much simpler and even faster than the BTree based solution, even for 100,000 requests (that is, we go through the whole slice and only process asks where pendingAskRepeat > 0).
BenchmarkBtree_SmallItemCount BenchmarkBtree_SmallItemCount-6 2143888 553.1 ns/op 80 B/op 4 allocs/op BenchmarkIteration_DontRemovePendingAskRepeat0 BenchmarkIteration_DontRemovePendingAskRepeat0-6 5071994 253.9 ns/op 0 B/op 0 allocs/op BenchmarkIteration_AlwaysSort BenchmarkIteration_AlwaysSort-6 3002 395433 ns/op 304 B/op 7 allocs/op
BenchmarkBtree_SmallItemCount walks a btree with 10 elements.
BenchmarkIteration_DontRemovePendingAskRepeat0 goes through a slice of 100,000 elements but only 10 of them are interesting to us.
BenchmarkIteration_AlwaysSort is what we have now.
If we factor in adding requests / re-sorts, it's still better to sort.