[
https://issues.apache.org/jira/browse/YUNIKORN-1719?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Peter Bacsko updated YUNIKORN-1719:
-----------------------------------
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).
{noformat}
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
{noformat}
{{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.
was:
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).
{noformat}
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
{noformat}
{{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.
> Improve the performance of Application.sortRequests()
> -----------------------------------------------------
>
> Key: YUNIKORN-1719
> URL: https://issues.apache.org/jira/browse/YUNIKORN-1719
> Project: Apache YuniKorn
> Issue Type: Sub-task
> Reporter: Peter Bacsko
> Assignee: Peter Bacsko
> Priority: Major
> Labels: pull-request-available
>
> 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).
> {noformat}
> 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
> {noformat}
> {{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.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
