6 ms·

I'm kind of speechless that "popping a message from the queue" requires knowing the length of the queue, which requires traversing the entire queue, a linked li

I'm kind of speechless that "popping a message from the queue" requires knowing the length of the queue, which requires traversing the entire queue, a linked list of as many as 90,000 elements. Even the "fast" time of about half a millisecond is crazy slow for dequeuing an item. If a linked list is a built-in Erlang data structure, why doesn't it keep a length count? If it's common knowledge that this operation is O(N), why does RabbitMQ call it on dequeue, and why doesn't it keep its own length count (and why isn't that the obvious fix)? I can't think of any JavaScript built-in (the language where I spend my days) with a name like "length" that internally dereferences N pointers, but I would not be shocked to discover that dereferencing tens of thousands of pointers was taking a few milliseconds, and I would not write my data structure that way.

deleted 12y ago
[deleted]
deleted 12y ago
[deleted]
Betelgeuse90 12y ago
Well, you do need to know that there exists an item in the queue. Knowing that length > 0 is one way to go about it, but certainly it's enough to establish the existence of one item and then move on. If one is unaware of the complexity of the .length() method, one might use it to find out if a dequeue is possible.
- rtpg 12y ago
  This seems like a pretty fundamental issue though. I'd feel like any systems programmer worth their weight in salt would know that yo can build an O(1) pop on a queue.
  - Betelgeuse90 12y ago
    If you don't think about the underlying implementation of erlang:length(), this seems to me like an easy mistake to make. Lots of data structures keep a size field and access it in O(1), so it's not completely unreasonable to expect erlang:length to be O(1) without making sure. At least that's how I understood the context of the problem, I may be wrong of course.
  - felixgallo 12y ago
    oh, I suspect they do. Which is why the manual page for erlang:queue talks about the topic in detail and explains the rationale, gives a workaround, and links to the literature. http://erlang.org/doc/man/queue.html http://erlang.org/doc/man/queue.html
    - rtpg 12y ago
      This talks about the O(n)-ness of length, but I don't see the rationale for the O(n)-ness of pop. Maybe I'm missing something?
      - felixgallo 12y ago
        You fell victim to the confusion in the original post and this thread between what the original poster describes as popping, and what they were apparently actually doing (which involved taking the length, which is O(N) for the reasons explained here and in the documentation). erlang's queue's pop ("out") is amortized O(1), worst case O(N) just like every other immutable double headed queue. Here's the source code: https://github.com/erlang/otp/blob/172e812c491680fbb175f56f7604d4098cdc9de4/lib/stdlib/src/queue.erl#L137 https://github.com/erlang/otp/blob/172e812c491680fbb175f56f7...
  - theoh 12y ago
    It's the functional way to believe that the elegance of a singly linked list means that it is the right choice for the implementation, instead of something more complex and unwieldy that can fold both ways in the same time, for example.
- fla 12y ago
  If you need to know if it's not empty, shoudn't it be easier to just test if the pointer to the first item is not-null ?
  - Betelgeuse90 12y ago
    Does erlang have pointers?
    - fla 12y ago
      I honestly don't know a thing about Erlang. But from my humble understanding of the interpreter source in the article: if is_list(list) is true, then the list is not empty. If you ask me, a respectable dequeue operation shoudn't need more than O(1).
      - lostcolony 12y ago
        No. In Erlang, is_list([]) is true. The correct implementation for checking if a list is empty would have been a pattern match, something akin to case List of [] -> empty; [_ | _] -> not_empty end. Or, you know. Reading the API docs and using queue:is_empty(Queue), which is O(1) instead of O(n) (which queue:len(Queue) is -explicitly stated to be-).
- deleted 12y ago
  [deleted]
  - dangrossman 12y ago
    > yet you can pick up a Bachelor's without ever hearing the word "allocate" What university has such a program? Programming language design (students write an interpreter and compiler), operating systems (students write a minimal OS including virtual memory management), systems architecture (students design a CPU and write some flavor of ASSEMBLY) and algorithms (students learn about time and memory complexity) are core, required courses in all the CS programs around here. They're required topics for a CS program to be accredited by ABET. Maybe you're confusing actual CS programs with trade school certificate programs; you don't get a bachelors in CS by writing some Java.
    - ZanyProgrammer 12y ago
      How important is ABET certification in the real world?
deleted 12y ago
[deleted]
lostcolony 12y ago
So this is only tangentially related, but it's all bloody neat, so I'm going to mention it anyway. First, keeping a length of a list, as part of the library implementation, is a bad idea, because due to how immutability works, you'd need to keep a length from -every item in a linked list-. That is, rather than [4, 3, 2, 1] you would need to have [{4, 4}, {3, 3}, {2, 2}, {1, 1}] Why? Because adding a new element to the head of a list needs to be O(1), -and- maintain the existing list. That is, if I have List1 = [4, 3, 2, 1]. I need to be able to do List2 = [5 | List1] That is, List2 is now [5, 4, 3, 2, 1] and List1 remains unaffected. So both List1 and List2 would need to still know their lengths, as would any other variables with heads further down in the list. So we have ~doubled the memory usage of a list, in that we need both a pointer (to the contents), and an integer, for each cell of the list. We can't simply store a 'total' value for a list (well, we could, and then every time we perform -any- operation on a list, that generates a new list(s) we re-calculate the length for it/them. Which would be a pain to code, results in a lot of extra garbage (since the intermediate values of the counter are thrown away, again, immutable), is unnecessary...and is actually impossible in lazy languages like Haskell that allow infinite lists. Quite frankly, in functional languages you don't need the length enough to go through such hassles, and when you do, yeah, it's easy enough to write it for your one use case). And that said, we don't need any of that noise for implementing an efficient queue. An immutable queue in Erlang is implemented via Okasaki's queue implementation (though with a recognizable API by default; Okasaki's API is still there). This is actually a really cool data structure, and has parallels to the interview question "how would you implement a (double ended) queue using two stacks". In short, it looks like this - {[], []}. Where you have a tuple of two elements; two lists (and an immutable list works identically to a stack; operations upon the head of it work in O(1) time) Enqueue 1 at the front -> {[1], []} Enqueue 2 at the front; note that this is actually stacking the 2 in front of the 1 -> {[2,1], []} Dequeue examines the second list, sees it's empty, reverses the first list, puts it in for the second (and an empty list in the first), and pops off the top of it, a la -> {[2,1], []} -> {[1, 2], []} -> {[], [1, 2]} -> {1, {[], [2]}} Where 1 is your return value, and {[], [2]} is the new queue. Further enqueues keep going onto that first list, dequeues come off the second, until it's empty, whereupon the first list is reversed again and placed in for the second. Etc. This has an amortized constant time enqueue and dequeue, despite being immutable, and a constant time 'is_empty' check, where you just check each list to see if it's empty or not (easily doable by checking to see if it pattern matches [] or [_ | _]. Pushing onto the start of the second list, and pulling off the first, allows you to work on the other end of the queue. So all your usual operations for a double ended queue work in the same big-O time as for the mutable implementation, but you maintain immutability. The problem here is that the implementation relied on an O(n) behavior, when all it needed was an O(1) one. While the article states "The problem is not with erlang:length() being slow. It’s about being unpredictably slow.", I would counter that asking for length when you just want to see if it's empty or not is INDEED the problem. Length explicitly tells you it will traverse the list, and yes, it makes no guarantees about where the elements of the list are in memory. Same as in every other language. Because contiguous pointers in memory are called "an array of pointers" not a "list of pointers". Note, too, that this article is from 2010. I'm guessing that basic.get has since been rewritten to not use an O(n) implementation when an obvious O(1) implementation exists.
old_sound 12y ago
This is not true anymore, linked blog post is from 2010. RabbitMQ doesn't work like that now. It has queue indexes and various mechanisms to keep messages in memory and so on.

deleted 12y ago

[deleted]

deleted 12y ago

[deleted]

Betelgeuse90 12y ago

Well, you do need to know that there exists an item in the queue. Knowing that length > 0 is one way to go about it, but certainly it's enough to establish the existence of one item and then move on. If one is unaware of the complexity of the .length() method, one might use it to find out if a dequeue is possible.

rtpg 12y ago
This seems like a pretty fundamental issue though. I'd feel like any systems programmer worth their weight in salt would know that yo can build an O(1) pop on a queue.
- Betelgeuse90 12y ago
  If you don't think about the underlying implementation of erlang:length(), this seems to me like an easy mistake to make. Lots of data structures keep a size field and access it in O(1), so it's not completely unreasonable to expect erlang:length to be O(1) without making sure. At least that's how I understood the context of the problem, I may be wrong of course.
- felixgallo 12y ago
  oh, I suspect they do. Which is why the manual page for erlang:queue talks about the topic in detail and explains the rationale, gives a workaround, and links to the literature. http://erlang.org/doc/man/queue.html http://erlang.org/doc/man/queue.html
  - rtpg 12y ago
    This talks about the O(n)-ness of length, but I don't see the rationale for the O(n)-ness of pop. Maybe I'm missing something?
    - felixgallo 12y ago
      You fell victim to the confusion in the original post and this thread between what the original poster describes as popping, and what they were apparently actually doing (which involved taking the length, which is O(N) for the reasons explained here and in the documentation). erlang's queue's pop ("out") is amortized O(1), worst case O(N) just like every other immutable double headed queue. Here's the source code: https://github.com/erlang/otp/blob/172e812c491680fbb175f56f7604d4098cdc9de4/lib/stdlib/src/queue.erl#L137 https://github.com/erlang/otp/blob/172e812c491680fbb175f56f7...
- theoh 12y ago
  It's the functional way to believe that the elegance of a singly linked list means that it is the right choice for the implementation, instead of something more complex and unwieldy that can fold both ways in the same time, for example.
fla 12y ago
If you need to know if it's not empty, shoudn't it be easier to just test if the pointer to the first item is not-null ?
- Betelgeuse90 12y ago
  Does erlang have pointers?
  - fla 12y ago
    I honestly don't know a thing about Erlang. But from my humble understanding of the interpreter source in the article: if is_list(list) is true, then the list is not empty. If you ask me, a respectable dequeue operation shoudn't need more than O(1).
    - lostcolony 12y ago
      No. In Erlang, is_list([]) is true. The correct implementation for checking if a list is empty would have been a pattern match, something akin to case List of [] -> empty; [_ | _] -> not_empty end. Or, you know. Reading the API docs and using queue:is_empty(Queue), which is O(1) instead of O(n) (which queue:len(Queue) is -explicitly stated to be-).
deleted 12y ago
[deleted]
- dangrossman 12y ago
  > yet you can pick up a Bachelor's without ever hearing the word "allocate" What university has such a program? Programming language design (students write an interpreter and compiler), operating systems (students write a minimal OS including virtual memory management), systems architecture (students design a CPU and write some flavor of ASSEMBLY) and algorithms (students learn about time and memory complexity) are core, required courses in all the CS programs around here. They're required topics for a CS program to be accredited by ABET. Maybe you're confusing actual CS programs with trade school certificate programs; you don't get a bachelors in CS by writing some Java.
  - ZanyProgrammer 12y ago
    How important is ABET certification in the real world?

deleted 12y ago

[deleted]

lostcolony 12y ago

So this is only tangentially related, but it's all bloody neat, so I'm going to mention it anyway. First, keeping a length of a list, as part of the library implementation, is a bad idea, because due to how immutability works, you'd need to keep a length from -every item in a linked list-. That is, rather than [4, 3, 2, 1] you would need to have [{4, 4}, {3, 3}, {2, 2}, {1, 1}] Why? Because adding a new element to the head of a list needs to be O(1), -and- maintain the existing list. That is, if I have List1 = [4, 3, 2, 1]. I need to be able to do List2 = [5 | List1] That is, List2 is now [5, 4, 3, 2, 1] and List1 remains unaffected. So both List1 and List2 would need to still know their lengths, as would any other variables with heads further down in the list. So we have ~doubled the memory usage of a list, in that we need both a pointer (to the contents), and an integer, for each cell of the list. We can't simply store a 'total' value for a list (well, we could, and then every time we perform -any- operation on a list, that generates a new list(s) we re-calculate the length for it/them. Which would be a pain to code, results in a lot of extra garbage (since the intermediate values of the counter are thrown away, again, immutable), is unnecessary...and is actually impossible in lazy languages like Haskell that allow infinite lists. Quite frankly, in functional languages you don't need the length enough to go through such hassles, and when you do, yeah, it's easy enough to write it for your one use case). And that said, we don't need any of that noise for implementing an efficient queue. An immutable queue in Erlang is implemented via Okasaki's queue implementation (though with a recognizable API by default; Okasaki's API is still there). This is actually a really cool data structure, and has parallels to the interview question "how would you implement a (double ended) queue using two stacks". In short, it looks like this - {[], []}. Where you have a tuple of two elements; two lists (and an immutable list works identically to a stack; operations upon the head of it work in O(1) time) Enqueue 1 at the front -> {[1], []} Enqueue 2 at the front; note that this is actually stacking the 2 in front of the 1 -> {[2,1], []} Dequeue examines the second list, sees it's empty, reverses the first list, puts it in for the second (and an empty list in the first), and pops off the top of it, a la -> {[2,1], []} -> {[1, 2], []} -> {[], [1, 2]} -> {1, {[], [2]}} Where 1 is your return value, and {[], [2]} is the new queue. Further enqueues keep going onto that first list, dequeues come off the second, until it's empty, whereupon the first list is reversed again and placed in for the second. Etc. This has an amortized constant time enqueue and dequeue, despite being immutable, and a constant time 'is_empty' check, where you just check each list to see if it's empty or not (easily doable by checking to see if it pattern matches [] or [_ | _]. Pushing onto the start of the second list, and pulling off the first, allows you to work on the other end of the queue. So all your usual operations for a double ended queue work in the same big-O time as for the mutable implementation, but you maintain immutability. The problem here is that the implementation relied on an O(n) behavior, when all it needed was an O(1) one. While the article states "The problem is not with erlang:length() being slow. It’s about being unpredictably slow.", I would counter that asking for length when you just want to see if it's empty or not is INDEED the problem. Length explicitly tells you it will traverse the list, and yes, it makes no guarantees about where the elements of the list are in memory. Same as in every other language. Because contiguous pointers in memory are called "an array of pointers" not a "list of pointers". Note, too, that this article is from 2010. I'm guessing that basic.get has since been rewritten to not use an O(n) implementation when an obvious O(1) implementation exists.

old_sound 12y ago

This is not true anymore, linked blog post is from 2010. RabbitMQ doesn't work like that now. It has queue indexes and various mechanisms to keep messages in memory and so on.