Spot the bug: javascript queue



  • (Slightly normalized) queue implementation from an advanced javascript book.

    var Queue = function () {
    	this.array= [];
    	this.head= 0;
    	this.tail= -1;
    };
    
    Queue.prototype.pushTail = function (value) {
    	return this.array[this.tail += 1] = value;
    };
    
    Queue.prototype.pullHead = function () {
    	var value;
    	if (!this.isEmpty()) {
    		value = this.array[this.head]
    		this.array[this.head] = undefined;
    		this.head += 1;
    		return value;
    	}
    };
    
    Queue.prototype.isEmpty = function () {
    	return this.tail < this.head;
    };
    

    Spot the bug!


  • FoxDev

    @cartman82 said:

    return this.array[this.tail += 1] = value;

    😷

    Also, the whole implementation just sits with me wrong; I just don't understand why they went with that as a design. If the queue is used often enough, you'll get integer overflow.


  • I survived the hour long Uno hand

    Specifically:

    @cartman82 said:

    this.tail= -1;

    @cartman82 said:

    this.head= 0;

    @cartman82 said:

    this.tail += 1

    @cartman82 said:

    this.tail < this.head;

    One item in the queue == "empty" queue.

    This is why bounds checking is useful! Unit tests on equivalence partitions should include boundary conditions pretty much always.



  • Nope.

    @RaceProUK said:

    Also, the whole implementation just sits with me wrong; I just don't understand why they went with that as a design. If the queue is used often enough, you'll get integer overflow.

    Maybe after 1000 years in most use cases. Seems like a fair trade for not having to do splice on each change.



  • @Yamikuronue said:

    One item in the queue == "empty" queue.

    This is why bounds checking is useful! Unit tests on equivalence partitions should include boundary conditions pretty much always.

    Nope.

    After a single push.

    // head === 0
    // tail === 0
    
    return this.tail < this.head; // false --> the queue is not empty
    

  • I survived the hour long Uno hand

    oh right, I misread that. My bad.


  • Banned

    pullHead() doesn't return anything if the queue is empty. Working or not, this looks bad and should be fixed.


  • FoxDev

    I spy a semicolon. Or rather, I don't: there's one missing on line 1 inside the empty check's block. But then I think JS has a feature where it adds 'phantom' semicolons, so that'd probably fix it.


  • FoxDev

    @Gaska said:

    pullHead() doesn't return anything if the queue is empty. Working or not, this looks bad and should be fixed.

    It's JavaScript, so there's an implicit return undefined; at the end of the method. I think.



  • @Gaska said:

    pullHead() doesn't return anything if the queue is empty. Working or not, this looks bad and should be fixed.

    Stylistic...

    @RaceProUK said:

    I spy a semicolon. Or rather, I don't: there's one missing on line 1 inside the empty check's block. But then I think JS has a feature where it adds 'phantom' semicolons, so that'd probably fix it.

    Stylistic...

    .. not the WTF I had in mind.


  • FoxDev

    the bug is the code reduces to this:

    var Queue = function () {
    	this.array= [];
    };
    
    Queue.prototype.pushTail = function (value) {
    	return this.array.push(value);
    };
    
    Queue.prototype.pullHead = function () {
    	return this.array.shift();
    };
    
    Queue.prototype.isEmpty = function () {
    	return this.array.length > 0;
    };
    

    or

    Array.prototype.pushTail = Array.prototype.push;
    Array.prototype.pullHead = Array.prototype.shift;
    Array.prototype.isEmpty = function () {
    	return this.length > 0;
    };
    Queue = Array;
    

  • Banned

    @RaceProUK said:

    It's JavaScript

    @cartman82 said:

    Stylistic...

    Saying it's OK to not return from conceptually non-void function is like saying it's OK to make errors in floating-point arithmetics.


  • BINNED

    pullHead (it's called pop, jeez), moves head ahead one and stacks undefineds in the beginning of the array instead or reusing the space?



  • @accalia said:

    the bug is the code reduces to this:

    Nope.

    @Gaska said:

    Saying it's OK to not return from conceptually non-void function is like saying it's OK to make errors in floating-point arithmetics.

    @RaceProUK said:

    It's JavaScript, so there's an implicit return undefined; at the end of the method. I think.

    RaceProUK is right.



  • @Onyx said:

    pullHead (it's called pop, jeez), moves head ahead one and stacks undefineds in the beginning of the array instead or reusing the space?

    BINGO!

    Memory leak galore.

    What he wanted was delete instead.


  • FoxDev

    @cartman82 said:

    Memory leak galore.

    I saw the memory leak… why didn't I say something?

    I r dispoit


  • FoxDev

    @cartman82 said:

    Nope.

    i'm still right in what that code reduces to!

    😛
    i may not have found the specific memory leak bug you found, but that just means the bug was in teh head of the developer!

    😆



  • javascript queue

    Found it!


  • BINNED

    I honestly thought you're going to have some explanation for that. It's such a beginner mistake, I honestly thought I'm just reading it wrong :P



  • After a 5 minute chrome test.

    The second one is fixed version.



  • @accalia said:

    i'm still right in what that code reduces to!

    Not exactly...

    Array.prototype.push returns the length of the array.
    Queue.prototype.pushTail returns the value added to the array.


  • Banned

    @cartman82 said:

    RaceProUK is right.

    I know that you can drive a car with broken hand brake just fine, and it's perfectly safe and all, but your car is still broken.

    Edit: also, the implicitly-returning-undefined code path doesn't use variable value. Another code smell.



  • @Onyx said:

    I honestly thought you're going to have some explanation for that. It's such a beginner mistake, I honestly thought I'm just reading it wrong

    That's why I created a simulation. Had to be sure this guy (who is much more experienced and better programmer than me) didn't know something I don't know.

    Nope. He just screwed up.


  • I survived the hour long Uno hand

    @Onyx said:

    t's called pop, jeez)

    Today I sat in a room full of Node.js developers (seriously, it was the Node.js meetup) who had no idea what streams were for and were confused about how you can save memory processing a chunk at a time when there's only one thread in node.

    I am never surprised by the lack of CS knowledge coming from the JS community.


  • Banned

    Wait. If I set array field to undefined, the then-bound-now-free object doesn't get GC'd? Or is it just Chrome not handling sparse arrays too well? Or are undefineds stored as separate objects in the table?



  • @accalia said:

    i'm still right in what that code reduces to!

    i may not have found the specific memory leak bug you found, but that just means the bug was in teh head of the developer!

    There's value in reducing the public interface to the essentials the consumer needs. Especially in a dynamic language, where any refactoring is a minefield of potential bugs.

    @Yamikuronue said:

    Today I sat in a room full of Node.js developers (seriously, it was the Node.js meetup) who had no idea what streams were for and were confused about how you can save memory processing a chunk at a time when there's only one thread in node.

    I'm not impressed by the level of skill in the node community. It's too often that I see some code and feel like I could have done a lot better. That never happened in the C# world (although most of the code there was either locked up or written my MS).



  • @Gaska said:

    Wait. If I set array field to undefined, the then-bound-now-free object doesn't get GC'd? Or is it just Chrome not handling sparse arrays too well? Or are undefineds stored as separate objects in the table?

    You add an array element that references undefined. That's not a sparse array.

    delete arr[index]
    

    This creates a sparse field in arr at index.

    When you then do

    arr[index]
    

    ... you get an undefined back. But that's a new undefined, generated by there being no element at index. Not an undefined that's a part of the array.


  • FoxDev

    @Onyx said:

    it's called pop, jeez

    Since it's a queue, it should really be dequeue, with pushTail being enqueue.

    Bonus: Like the way .NET has a class called Queue<T> 😆


  • BINNED

    @RaceProUK said:

    Since it's a queue

    And yet it has no methods to do anything other than push and pop. Can someone explain to me what, in this specific case, is the difference to a stack? Unless there are methods which were not posted, of course.


  • FoxDev

    @Onyx said:

    Can someone explain to me what, in this specific case, is the difference to a stack?

    Other than being FIFO instead of FILO?


  • FoxDev

    @RaceProUK said:

    Queue<T>

    😊


  • BINNED

    @RaceProUK said:

    Other than being FIFO instead of FILO?

    Ah, see, that would involve thinking about the code. I think I broke my brain for tonight while writing that abomination in C...


  • BINNED

    Third result for Qt on GIS is from www.tizenexperts.com :wtf:


  • FoxDev

    @Onyx said:

    Ah, see, that would involve thinking about the code

    Really? I just go by the definition of queue and stack as they are in a dictionary 😛


  • BINNED

    @RaceProUK said:

    Really?

    You know what I think of when you say "queue" these days?

    But yeah, I should have known that. Whatever, I know what FIFO and LIFO are, I'm sure I could manage on the googles :P


  • Banned

    @cartman82 said:

    You add an array element that references undefined. That's not a sparse array.

    delete arr[index]

    This creates a sparse field in arr at index.

    When you then do

    arr[index]

    ... you get an undefined back. But that's a new undefined, generated by there being no element at index. Not an undefined that's a part of the array


    That's just plain stupid. If out-of-bounds index returns the same value as the index set to undefined, what's the point of storing the value any longer? And if they're two separate objects, is there a way to differentiate between them? Why would you even want to?



  • Once you have your collections return some kind of value for out of bounds / element not found condition (instead of throwing an error), and you can store that value in a var, there's inevetably a question of what happens when you return that value back into the collection.

    It's a subtle behavior that is often a cause of gotchas and bugs. But for good or ill, it is often seen in dynamic languages. There are upsides too, like avoiding try/catch blocks or double call "is there a value / get the value".

    And yes, all undefineds are equal. The difference is, in first case the array stores references to this singleton value, while in a sparse array, there's just nothing at these indexes (thus no memory loss).


  • Banned

    Returning undefined absolutely makes sense. What doesn't make sense is treating a field that holds undefined value and field that holds undefined value differently. Lua does it correctly - assigning nil to table key effectively removes it. Why doesn't V8 do the same? V8, not JS, because it's implementation detail - unless deleted value and undefineded value make semantical difference that actually affects code.



  • Semantic simplicity: a set operation is always a set operation and always behaves exactly the same way regardless of argument, even if the argument is of type undefined or even a literal undefined. This means the only way to deallocate, besides garbage collection, is delete, but it also means the heavily-used assignment operator has a lower cyclomatic complexity, which -- since we're not on Itanium and don't have predicate registers -- actually is important.

    Or something, I dunno. Hey, V8 is a delicious beverage I should go drink some...


  • Banned

    @TwelveBaud said:

    Semantic simplicity: a set operation is always a set operation and always behaves exactly the same way regardless of argument, even if the argument is of type undefined or even a literal undefined

    Works this way in Lua too.

    @TwelveBaud said:

    the heavily-used assignment operator has a lower cyclomatic complexity, which -- since we're not on Itanium and don't have predicate registers -- actually is important

    Classic cpu-memory tradeoff. It's neither better or worse than treating undefined in arrays special - it's just better in some cases and worse in others. But in the age of JITs, I'd risk a claim that CPU cost growth would be negligible, while memory usage would drop significandly here. But you can't know that without profiling both.



  • @Gaska said:

    But in the age of JITs, I'd risk a claim that CPU cost growth would be negligible, while memory usage would drop significandly here.
    Memory use would definitely drop significantly, and in the case of setting something to the literal undefined the JITter absolutely can make that syntactic sugar for delete at no penalty. But for the wider universe of values that can be Maybe<undefined>s, the JITter can't assume one way or the other, and pops in a branch. And since a branch prediction miss stalls the pipeline for several dozen instructions (remember, no predicate registers, so we have to jump), and the relevant code could theoretically be for an array of color values in a pixelData object, that's a pretty significant price to pay.

    But you're right; I don't have a Jaegermonkey profile handy, so I'm making performance assumptions without data. Still, interesting intellectual exercise, and it explains one possible reason why V8 is the way it is.



  • @Gaska said:

    Semantic simplicity: a set operation is always a set operation and always behaves exactly the same way regardless of argument, even if the argument is of type undefined or even a literal undefined

    Works this way in Lua too.

    No, it actually doesn't. Tell me, will this print anything or not when called?

    function doStuff(k, v)
        local t = {}
        t[k] = v
        for k2, v2 in pairs(t) do
            print(k2, v2)
        end
    end
    

    Answer: It will print the passed key and value only if the value is not nil. By contrast, the JavaScript equivalent would always print the passed key and value.



  • @Gaska said:

    That's just plain stupid. If out-of-bounds index returns the same value as the index set to undefined, what's the point of storing the value any longer? And if they're two separate objects, is there a way to differentiate between them? Why would you even want to?

    QFT. What Cartman is saying is that there's null, and then there's undefined, and then there's "really undefined" (aka FILE_NOT_FOUND?) Having two of these already doesn't make sense, but three...



  • This is almost exactly like Python's None global. Let's review.

    • null = A signal that a field is present, but information is not available for that field. Implemented for compatibility with Java's own null, when it was being positioned as a supplement for applets. Also useful for databases or non-Java lightweight proxies.

    • "really undefined" = Really undefined. Since JS is a dynamic language, it's possible to, without reflection, attempt to access nonexistent members, and throwing a NoSuchMethod/FieldError would ... I dunno, I guess alter flow control in an unexpected way. I don't have Brendan Eich on speed dial, but let's say for the sake of argument that this makes sense.

    • undefined = A signal that you've tried to access something that's really undefined. It's implemented as a read-only global. Because it's a thing that exists, you can assign it to stuff. This is over and above the engine returning it for things that are "really undefined", letting it propagate it through assignments until you try to dereference it.



  • Array;
    

    There, no bugs.



  • var x map[int]int = nil
    y, ok := x[1]
    fmt.Println(y, ok) // 0, false
    fmt.Println(x[1]) // 0
    
    x = make(map[int]int)
    y, ok = x[1]
    fmt.Println(y, ok) // 0, false
    fmt.Println(x[1]) // 0
    
    x[1] = 42
    y, ok = x[1]
    fmt.Println(y, ok) // 42, true
    fmt.Println(x[1]) // 42
    


  • Fields that hold undefined and empty fields act differently with reflection and iteration.

    Could they have made x[i] = undefined act the same as delete x[i]?

    The best I can tell, yes.

    So why didn't they?

    Rush? Some gotcha I don't see ATM? Dunno.



  • @Gaska said:

    deleted value and undefineded value make semantical difference that actually affects code.

    Yes.

    This is a javascript :wtf: that has been :headdesk: many times :facepalm:.


  • Banned

    @immibis_ said:

    Answer: It will print the passed key and value only if the value is not nil

    I like to imagine Lua tables as infinite sets of key-value pairs that already have every possible key present, all initially set to nil. With this model, assigning values to keys is perfectly consistent, and skipping the nils absolutely makes sense (otherwise, for-each loop would never terminate).


  • Banned

    @cartman82 said:

    Fields that hold undefined and empty fields act differently with reflection and iteration

    Ah, now that's wholly different. If iteration exposes different behavior when delete and undefined are used, then it would be wrong to auto-delete undefineds.

    TRWTF is of course "meaningful" undefined.


Log in to reply