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

Fredrik <>
Tue Jan 15 17:38:01 CET 2013


Thanks,
Will try to build and put it in the 'master-pu' branch if successful today.

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
> 
> http://erlang.org/mailman/listinfo/erlang-patches

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-patches/attachments/20130115/e044134e/attachment.html>


More information about the erlang-patches mailing list