[erlang-patches] [patch] Fix bug in stdlib/queue that can slow down out/out_r

[Fredrik]

Hello,
Your patch has been to review,
" The idea seems good but the list is broken apart and rebuilt. It 
should look like: r2f(List) -> {FF,RR} = lists:split(length(List) div 2 
+ 1, List), {FF,lists:reverse(RR, [])}."

Could you fix this?

BR Fredrik Gustafsson
Erlang OTP Team
On 01/15/2013 05:09 PM, Alex Erofeev wrote:
> When applying out/out_r methods if one list of queue is empty can 
> happen situation where big list will be copying each time, so instead 
> on amortized linear time we'll get O(N^2). Example: 
> https://gist.github.com/4539653 . Try running it with 100000, 1000000 
> and 10000000 elements and compare run times.
> So I changed internal functions r2f and f2r to copy each time only 
> half of list instead of almost all of it.
>
> git fetch https://github.com/AlexErofeev/otp/tree/faster_queue
> https://github.com/AlexErofeev/otp/compare/faster_queue
> https://github.com/AlexErofeev/otp/compare/faster_queue.patch
>
> Regards,
>
> Alex Erofeev
>
>
> _______________________________________________
> erlang-patches mailing list
> erlang-patches@REDACTED
> http://erlang.org/mailman/listinfo/erlang-patches

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-patches/attachments/20130117/aa27e70b/attachment.htm>