In Ruby, the "*" operator used with a string on the left and a number on the right does string repetition. "Ruby"*2 evaluates to "RubyRuby", for example. This is only occasionally useful (when creating lines of hyphens for ASCII tables, for example) but it seems kind of neat. And it sure beats having to write a loop and concatenate n copies of a string one at a time--that just seems really inefficient.
I just realized that there is a clever way to implement string multiplication in JavaScript:
String.prototype.times = function(n) {
return Array.prototype.join.call({length:n+1}, this);
};
"js".times(5) // => "jsjsjsjsjs"
This method takes advantage of the behavior of the Array.join() method for arrays that have undefined elements. But it doesn't even bother creating an array with n+1 undefined elements. It fakes it out using and object with a length property and relies on the fact that Array.prototype.join() is defined generically. Because this object isn't an array, we can't invoke join() directly, but have to go through the prototype and use call(). Here's a simpler version that might be just as efficient:
String.prototype.times = function(n) { return (new Array(n+1)).join(this);};
When you call the Array() constructor with a single numeric argument, it just sets the length of the returned array, and doesn't actually create any elements for the array.
I've only tested these in Firefox. I'm assuming that either is more efficient than anything that involves an actual loop, but I haven't run any benchmarks.
Some recent optimizations to [].join all but certainly make this faster than the raw loop (in Firefox 3.6, that is; 3.5 has a much less optimized algorithm about which I will make no predictions). Then again, you could potentially lose; since the hole case is going to be otherwise extremely uncommon for most arrays, the loop inside Array.prototype.join that you're going through is going to hit the not-taken if-hole branch every time, and on modern CPUs that's going to pay a heavy penalty for the branch misprediction and pipeline flush or stall that accompanies it, assuming that branch choice is already cached by the CPU from other join calls elsewhere in your code.
As for which is faster, I suspect the latter because the property-lookup misses in the latter case might be faster, integer indexes and all that, but I'm not sure. The most relevant metric is probably one method call versus two, but the property lookups lean the other way. The latter has a small amount of win from avoiding a couple extra data structures needed for the length mockup, which might but probably doesn't make a difference.
Even ignoring all that, it seems unlikely to me the minuscule amount of time you'll spend inside this method in actual use cases will appear on profiles, which is what really matters here.
Finally note that if you just test these inside loops the JIT will basically boil away the method calls and property lookups, so they'll more or less be equivalent, I bet.
An actual loop may faster. I run that code in "Google Chrome", the first method used 2 seconds, and the other one less 1 seconds.
String.prototype.times = function(n) {
return Array.prototype.join.call({length:n+1}, this);
}
document.write(new Date() + "");
"js".times(Math.pow(2, 23));
document.write(new Date() + "");
var abc = "js";
for ( var i = 0; i ");
String.prototype.times = function(n) {
return Array.prototype.join.call({length:n+1}, this);
}
document.write(new Date() + "");
"js".times(Math.pow(2, 23));
document.write(new Date() + "");
var abc = "js";
for ( var i = 0; i ");
String.prototype.times = function(n) {
return Array.prototype.join.call({length:n+1}, this);
}
document.write(new Date() + "<br>");
"js".times(Math.pow(2, 23));
document.write(new Date() + "<br>");
var abc = "js";
for ( var i = 0; i < 23; i++ ) {
abc += abc;
}
document.write(new Date() + ""<br>");
Jeff,
I thought the efficiency question was an interesting (if academic) one. Thanks for the insight into the Firefox implementation. I hadn't considered the issue of CPU branch caching!
David
redraiment,
That's not a fair test: you're using a special case that only works for values of n that are powers of 2!
what about this one, I think it can process all the case, and ... it's ugly.
String.prototype.times = function(n) {
if ( n == 1 ) {
return this;
}
var midRes = this.times(Math.floor(n/2));
midRes += midRes;
if ( n % 2 ) {
midRes += this;
}
return midRes;
}
Branch prediction is simultaneously one of the most exciting and most discouraging features of modern CPUs. I'm not surprised you hadn't considered it. For us deep in JS engine-land, however, it's a constant consideration. All the modern JS engines these days are butting up against branch prediction issues inside JITs and, perhaps surprisingly, sometimes outside it given opcode patterns that appear with enough frequency (there's usually a branch after a comparison in JS, for example, so SpiderMonkey optimizes that one). I wish it were possible, but there are no JITs for idealized machines (not now, probably not ever), except by incidence.
Actually, this is exactly how `times` is implemented in Prototype, only via `new Array` and then `join`, not just `join`.
I think we can do even better and reuse existing object, rather than create it on every function invocation. It will probably make things faster and more importantly, lower memory consumption.
String.prototype.times = (function(){
var join = Array.prototype.join,
obj = { };
return function(n) {
obj.length = n + 1;
return join.call(obj, this);
}
})();
Kangax,
Hmm. I thought this idea occurred to me spontaneously yesterday, but it could well be that I saw it first in the prototype code...
The optimizations you propose seem appropriate for a highly optimized library like Prototype (though I'd be curious to see benchmarks about optimizing the lookup of Array.prototype.join). But for my purposes here, I didn't want to go that deep.
redraiment,
You're right. Using string doubling is faster. See the next entry.
David
"js".times(5)
13 chars
"jsjsjsjsjs"
12 chars
Also much much faster, easy on the eyes and I tend to get it right the first time.
gaby,
True when the multiple is a constant. But imagine writing code to print ASCII tables where the column width depends on the (variable) column content. Then you end up having to create variable-length strings of hyphens. That's the sort of use-case I imagine for string multiplication. I'm not sure that I've ever had to do it myself, though. And I know that for an ASCII table, I could start with a string of 80 hyphens and use substring() to get any length from 1 to 80.