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

Alex Erofeev <>
Tue Jan 15 17:09:51 CET 2013


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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-patches/attachments/20130115/3a6a5203/attachment.html>


More information about the erlang-patches mailing list