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!
-
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.
-
Specifically:
this.tail= -1;
this.head= 0;
this.tail += 1
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.
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.
-
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
-
oh right, I misread that. My bad.
-
pullHead() doesn't return anything if the queue is empty. Working or not, this looks bad and should be fixed.
-
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.
-
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 implicitreturn undefined;
at the end of the method. I think.
-
pullHead() doesn't return anything if the queue is empty. Working or not, this looks bad and should be fixed.
Stylistic...
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.
-
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;
-
It's JavaScript
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.
-
pullHead
(it's called pop, jeez), moveshead
ahead one and stacksundefined
s in the beginning of the array instead or reusing the space?
-
the bug is the code reduces to this:
Nope.
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.
It's JavaScript, so there's an implicit return undefined; at the end of the method. I think.
RaceProUK is right.
-
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.
-
-
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!
-
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.
-
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.
-
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.
-
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.
-
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.
-
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 areundefined
s stored as separate objects in the table?
-
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.
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).
-
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
atindex
.When you then do
arr[index]
... you get an
undefined
back. But that's a new undefined, generated by there being no element atindex
. Not an undefined that's a part of the array.
-
it's called pop, jeez
Since it's a queue, it should really bedequeue
, withpushTail
beingenqueue
.Bonus: Like the way .NET has a class called
Queue<T>
-
Since it's a queue
And yet it has no methods to do anything other than
push
andpop
. 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.
-
Can someone explain to me what, in this specific case, is the difference to a stack?
Other than being FIFO instead of FILO?
-
Queue<T>
-
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...
-
Third result for Qt on GIS is from
www.tizenexperts.com
-
Ah, see, that would involve thinking about the code
Really? I just go by the definition ofqueue
andstack
as they are in a dictionary
-
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
-
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).
-
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
undefined
ed 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...
-
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.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.
-
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.
-
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.
-
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'sundefined
, 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 ownnull
, 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 asdelete x[i]
?The best I can tell, yes.
So why didn't they?
Rush? Some gotcha I don't see ATM? Dunno.
-
deleted value and undefineded value make semantical difference that actually affects code.
Yes.
This is a javascript that has been many times .
-
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).
-
Fields that hold undefined and empty fields act differently with reflection and iteration
Ah, now that's wholly different. If iteration exposes different behavior whendelete
andundefined
are used, then it would be wrong to auto-deleteundefined
s.TRWTF is of course "meaningful" undefined.