JavaScript: Search and Don’t Replace (2008) | Hacker News Reader

JavaScript: Search and Don’t Replace (2008)

johnresig.com

42 pointssven21243 comments

We probably should be cautious reading anything about JS optimization that's 12 years old. It might have been true at the time, but now with the highly-optimized V8 engine, and a set of native methods that didn't exist back then, there's a pretty good chance there's another way to do this that's even faster.

It can certainly be done at least as fast and much more legibly. Probably not in 2008 - which predates even ES5 by a year! - but these days, most certainly.

That is very true. I wrote a polygon drawing library the same year of this blog post, and I pulled out all the stops to make it as fast as possible on the browsers of the day - including IE6!

Now of course many of the tricks I used backfire in modern engines, and simple straightforward code is faster.

Perhaps a more important point is that this particular problem does not need to be optimized, and shouldn't be optimized! It should use the simplest and most understandable code possible. Even in the era of slow browsers from 10-15 years ago.

It's a query string, not a million-row database.

Truer words! I did a quick microbench of a few implementations of this and found that Resig's implementation is far from the best performance possible. PSA: Microbenchmarks are not indicative of real world performance

Find the code here: https://gist.github.com/rezonant/639c67db5bd6503e8f022291b91...

Results on my system (Core i7 7700, Node.js 10.15.3, Windows 10 2004):

---- Comparing 7 implementations, 1000000 repetitions each

  short input:
      resig: 2920ms
      resigModernized: 2369ms
      fullyFunctional: 2817ms
      functionalHybrid: 2352ms
      mapReduce: 5002ms
      splitmap: 1490ms
      compressURL: 6064ms
  long input, few keys:
      resig: 28664ms
      resigModernized: 23087ms
      fullyFunctional: 17509ms
      functionalHybrid: 18431ms
      mapReduce: 46959ms
      splitmap: 14791ms
      compressURL: 24485ms
  long input, many keys:
      resig: 17468ms
      resigModernized: 15049ms
      fullyFunctional: 15781ms
      functionalHybrid: 13768ms
      mapReduce: 30352ms
      splitmap: 12959ms
      compressURL: 34180ms

----

The winner (according to this crude benchmark) is this implementation:

  function splitmap(data){
      let q = new Map();
      for (let [key, value] of data.split(/&/g).map(x => x.split(/=/))) {
          q.set(key, `${q.has(key) ? q.get(key) + ',' : ''}${value}`);
      }
  
      let ret = "";
      for (let [ key, value ] of q)
          ret = `${ret ? ret + '&' : ''}${key}=${value}`;
      return ret;
  }

...but I'm sure folks can come up with something faster

EDIT: The splitmap() implementation will fail on key=value=foo, cutting off the extra "=foo", though if you are expecting valid URL-encoded params then this might be an acceptable limitation.

He missed an opportunity to make that even shorter and even more of a clusterfuck.

I present to you:

    function compress(data){
        var s = {}, q = [];
        data.replace(/([^=&]+)=([^&]*)/g, function(m, k, v) {
            s[k] ? q[s[k] - 1] += "," + v : s[k] = q.push(m);
        });
        return q.join("&");
    }

I think he avoided the array + join on purpose and went directly for final string concatenation :)

Further fucked:

        function compress(data){
            return data.replace(/(?<=(\w+)=[^&]*)&\1=/g,',');
        }

I say: do replace after all!

(Javascript didn't have zero-width look-behinds at the time)

That doesn't handle strings like

    foo=1&foo=2&foo=3&blah=a&blah=b&foo=4

correctly. You'd expect

    foo=1,2,3,4&blah=a,b

but get

    foo=1,2,3&blah=a,b&foo=4

I don't think it's possible to solve this just using a single search/replace.

It wasn't clear from the post whether that was a valid input. If it is, some parts would need to be re-ordered, making it a very fancy search/replace indeed. But I still think it's possible. One or two replacements to switch the ordering, and then my original one to get the final output.

I put some effort into trying to find a search/replace to do it. Without a high-powered replacement function, I couldn't do it. But I did do this instead.

        function compress(data){
            return data.split`&`.sort().join`&`.replace(/(?<=(\w+)=[^&]*)&\1=/g,',');
        }

That's a really creative way to do it!

Just use match instead? Why use replace and hack into an array?

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

To not create a intermediate array I think

This works fine:

[...paragraph.matchAll(regex)].reduce((q,[kv, key, value]) => { q[key] = (q[key] ? q[key] + `,`: ``) + value return q }, {})

https://pastebin.com/yb5QBCm6

It does, but it still creates an intermediate array which is what the parent comment was suggesting the use of `replace` worked around.

With that said, there could easily be an array being iterated under the hood with the `replace` method anyway.

In this case you can use for..of. The Array [... ] restructuring is converting the iterator to array so you can use reduce... but then you are using reduce in an imperative way. With for...of you skip the intermediate array and is more readable.

For...of has a bad rep because eslint usually is configured to show a warning, because the Babel transpile creates less optimal code if it targets old browsers; but is better here.

This was a time when there was widespread belief that iterating over an array was best done with a library.

I know it's weird, but that's what $.each existed for. for ... of did not exist.

There was a bit more to $.each than that.

Originally, a jQuery object that you got from calls like $(foo) was not an array-like object as it is today. The jQuery object had an internal array of the matching DOM elements, but you were supposed to ignore it and instead use $(foo).each(...) to iterate through the elements, or $(foo).get(n) to access a specific element.

I thought it would be more convenient if you could just treat the jQuery object itself as an array, which turned out to be a simple change. So that's why you can now do $(foo)[n]. The .get(n) method was kept for compatibility with very old code.

At that point, $(foo).each(...) was not as useful as it had been, but it was also kept for compatibility. And $.each(...) was also kept around, as it was the helper function for $(foo).each(...) and related methods.

Another fun fact on the first version of the jQuery code: all of the methods on a jQuery object like $().each, $().html, $().css, etc. were not on a prototype object. Whenever you called $(foo) to create a jQuery object, it ran a loop to copy references to all those methods into the jQuery object.

Needless to say, that was a bit slow, and got slower as you added plugins. So my other minor architectural contribution was to use a prototype instead of copying all the methods.

We were all learning as we went along in those days! :-)

.match() only returns the result of one match, rather than all the matches in the string. To do that, you'd need to use .matchAll() (which didn't exist in 2008), or write an awkward do…while loop. Using .replace() looks neater.

I would parse it and then re-stringify it and stop there until someone gets upset about performance.

I would have come up with something like this:

Object.entries(Array.from(new URLSearchParams("foo=1&foo=2&foo=3&blah=a&blah=b").entries()).reduce((a,[k,v]) => ({ ...a, [k]: [...a[k] ?? [], v] }), {})).map(([key, values]) => `${key}=${values.join(",")}`).join("&");

Things sure have changed in the last 12 years! The only method you're using that existed back then is join. Wild.

If you read the article he makes a point about not using intermediate arrays and .join()

That's a good point, but my post didn't have any grand point :)

I was hoping other people to come up modern solutions to this same original problem.

Even my solution is questionable, because it relies on generating new URLSearchParams with strings, if one wants to be secure the reduce should take URLSearchParams as accumulator and add the items there.

Is creating an array really more costly than altering a string? I think it may depend on how much condensing of params you expect compared to singular params. The things being optimized for also may have changed over the intervening decade. That's the problem with optimizing something without respect for it's intended common workload, or expecting those justifications to hold over time in all cases.

Edit: Woah, made a hash of that before going in and fixing all the typos from my phone keyboard.

I don't think this was posted as "I would submit a PR with this code for prod" but more of a "here's a cool one-liner for fun" approach.

I enjoy reading people's off-the-cuff code golf stuff and usually learn something.

> .reduce((a,[k,v]) => ({ ...a, [k]: [...a[k] ?? [], v] }), {}))

Note that this unfortunately common pattern is quadratic, which is usually not a good idea, and can have conflicts between entries and properties of Object.prototype. A similar implementation without those problems:

  .reduce((a, [k, v]) => a.has(k) ? a.set(k, [v]) : (a.get(k).push(v), a), new Map())

And an alternate implementation:

  const input = new URLSearchParams("foo=1&foo=2&foo=3&blah=a&blah=b");
  const result = new URLSearchParams();

  for (const key of input.keys()) {
    if (!result.has(key)) {
      result.set(key, input.getAll(key).join(","));
    }
  }

  return String(result);

This is the sort of thing that's cited when people say they hate Perl. I'd consider a more readable version if performance isn't really a 1st class requirement. It doesn't appear to be in this case. A temporary array solution would be much more readable.

Still quite a straightforward and elegant solution, but I'm curious what the performance is like these days compared to alternatives. The better the JIT gets, the more allocation (of the many intermediate strings, and the thrown-away string) would seem to matter.

If I remember right, the intermediate string version was already a reflection of the shifting interpreter landscape. I distinctly remember learning to always prefer Array#join for these kinds of things in 2006 or so for the same reason cited in the post.

Of course, that could have been based on a misunderstanding on the part of the person talking with me, though I would guess it matters how many intermediates (or array elements) you're talking about.

Sort of a miracle that you mostly don't need to worry about this stuff today, even running on a $100 mobile device.

> Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.

Jamie Zawinski

This is a funny quote. I really hope it doesn't keep people from learning regular expressions, which are actually not as hard as they are often portrayed and extremely powerful and efficient, as demonstrated in this post.

Sure it's powerful and a lot of them are easy. But there's a lot of indecipherable regexes in the wild. I guess you need to learn them anyway, but I'm very strict about using them in production

This is probably an ideal case though. Regular expressions are a part of the JavaScript standard, so there's no excuse for someone that programs in JavaScript to not know at least the basics, and this is almost as basic as you can get.

The alternative is what, a simple tokenizing parser? I think that's actually a step squarely into territory of making it more complex and less readable than a simple regular expression is.

the song of re̸gular exp ression parsing will exti nguish the voices of mor tal man from the sp here

https://stackoverflow.com/questions/1732348/regex-match-open...

> He wrapped himself in quotations - as a beggar would enfold himself in the purple of Emperors.

Kipling

I'd normally bristle against RegExp hate (unless the RegExp is complex), but in this case, please, just use `URLSearchParams`.

It's well-adopted (unless you have to support IE: <https://caniuse.com/?search=URLSearchParams>)

I’m so grateful for modern JS!

Please give me an 80 kloc project full of this kind of smartness, preferably minefied.

look at jQuery... if you have never read the source for it, as a developer, you are doing yourself an injustice. not only has john resig worked on it, but also yehuda katz, so there are some really smart people who coded it to learn from.

In my opinion, having read parts of jQuery's source code on various occasions… You should only read it for entertainment value, it makes for fascinating brain teasers. Here's one snippet I had the opportunity to read recently:

  contains = hasCompare || rnative.test( docElem.contains ) ?
    function( a, b ) {
      var adown = a.nodeType === 9 ? a.documentElement : a,
        bup = b && b.parentNode;
      return a === bup || !!( bup && bup.nodeType === 1 && (
        adown.contains ?
          adown.contains( bup ) :
          a.compareDocumentPosition && a.compareDocumentPosition( bup ) & 16
      ));
    } :
    function( a, b ) {
      if ( b ) {
        while ( (b = b.parentNode) ) {
          if ( b === a ) {
            return true;
          }
        }
      }
      return false;
    };

i have no doubts. i haven't read through the source in years, but i'm sure there are tons of wtfs in there. those dudes had to do some pretty effed up stuff in order to make it work, and keep working, with the slew of browsers and incompatibilities back then.

Reply on news.ycombinator.com