Hacker News new | comments | ask | show | jobs | submit login

You know, it's funny how it's 2015 and we're just dripping with raw power on our developer machines, yet, open a few hundred kilobytes of text and accidentally invoke a handful of O(n^2) algorithms and blammo, there goes all your power. Sobering.

Edit: We need a type system which makes O(n^2) algorithms illegal. (Yes... I know what I just dialed up. You can't see it, but I'm giving a very big ol' evil grin.)

It's also funny to see these techniques being reinvented and called optimisations, when perhaps 30 years ago they would not even be considered optmisations but the only possible way to do it, because anything else would be ridiculously slow to the point of being unworkable.

For example, the find and replace package uses markers to highlight search results, and if you ran a search for the letter e in a large file, the excessive time spent updating thousands of markers on every keystroke was intolerable

This suggests another problem they have is a huge constant, in addition to the algorithmic one --- "thousands" shouldn't be something a modern machine would choke on, if updating positions is a simple operation like increasing their offset by 1 after a character is inserted. On a CPU that can do one billion instructions per second (a good OOM estimate, which still underestimates how fast real CPUs today are by a few times), adding 1 to 10000 variables should not take any perceptible amount of time --- less than a millisecond.

Going from 800ms to 50ms is a great improvement, but I think that's still several orders of magnitude slower than what the machine can really do.

> This suggests another problem they have is a huge constant, in addition to the algorithmic one --- "thousands" shouldn't be something a modern machine would choke on, if updating positions is a simple operation like increasing their offset by 1 after a character is inserted.

As I mentioned in the article, a big part of the cost was updating a different interval storage structure as the markers were updated since the absolute positions approach left us no way to defer it.

Or if you use a continuously-fading color in the CSS for your extension (e.g. Rainbow selection), it'll eat 100% of one core just to change the background color on some text. It's a fun extension, but when my fan spins up because I forgot to deselect before switching windows, it kinda makes it less fun.

Hi there. I'm the author of that admittedly ridiculous and unnecessary extension :)

"Extension" should probably be in scare quotes because the implementation is literally just CSS animation: https://github.com/dmnd/rainbow-selection/blob/master/styles...

There's no good reason such an animation should be taxing your machine. It works fine on my MacBook Pro. But someone else reported this issue too: https://github.com/dmnd/rainbow-selection/issues/3

If you're interested in working out what's going on, please respond to that github issue. I understand if you don't want to spend time on such a trivial thing. But you spent the time to write this comment, so I figured maybe you're interested :)

so cool, installed immediately

Also known as the paste minified javascript in Jetbrains ide effect.

IntelliJ forks handle pasting large volumes of text much better than vim or sublime text in my opinion. IntelliJ will be able to maintain performant syntax highlighting because it builds an ast and does not use regular expressions.

The problem is not volume but extremely long lines. Minified js is one veeery long line. I think that they have some O(n^2) in their line algorithm. You can paste 60-70 thousand lines and it will highlight instantly. The same code minified will hang the IDE.

On a side note, you should preserve some new lines in your minified js as it makes dealing with production JavaScript errors much easier, assuming you have some kind of onerror hook that sends you js errors. The new lines don't add much to the overall size of your js but they make debugging much easier.

We have been meaning to get around to looking into this on my current project but haven't yet: I believe the browser's error event will return a column number.

> Column numbers in Firefox. Firefox is the only browser that doesn't support column numbers for exceptions. This makes debugging minified javascript essentially impossible. I've sent one patch but there's a lot more to do.


- written in 2014

but MDN now says:

> Column number for the line where the error occurred (number) - Requires Gecko 31.0


If anybody has live experience with this, I'm eager to hear about it.

Yes you get column numbers and that really helps as well, but as mentioned new lines don't really hurt that much and I'd rather have some new lines than none. In response to others about using source maps, I'm talking about production errors received from users in the wild who may or may not have source maps enabled in their browser.

Thats what I do, too. It makes debugging so much easier, and you can safe yourself the pain of source maps. A few bytes I gladly spend on keeping my sanity.

I've always wondered why minifiers don't take advantage of ASI to this effect. Your files come out the exact same size as cramming it onto a line with semicolons...

You should use source maps

Tell that to the people that pack jQuery ...

I've never thought about it that way. This makes web dev in Eclipse suddenly make so much more sense.

I'm a hue PyCharm fan, but if this is true then vim and Sublime must be barely usable. Python, it's great at...but open a big JS file and it...will...take...forever...to do the JS syntax highlighting, if it ever finishes. CoffeeScript is even worse, and almost always crashes.

It's always a little weird, because I have no performance issues anywhere else in it, and it's got ~7GB of RAM it could use.

I use PyCharm every day and IntelliJ and I have never had this problem. Maybe it's a resource issue with your hardware though and your version of Java. I use the new versions that bundle OpenJDK on a newer Macbook Pro.

It's amazing how true this is, huge files work fine, but one long line... I wish I knew more about editors to help fix it.

Yeah, I actually looked at atom sometime back. They have a problem with long lines because their regex engine runs in O(n^2). I suggested that they switch to a regex engine that runs in O(n). https://github.com/atom/atom/issues/979#issuecomment-7770371...

I don't know what happened after that. Maybe they will act on this. The only problem with the O(n) engine was that a lot of TextMate grammars for languages wouldn't work with atom but that was easily resolvable by writing them anew.

Let's say your CPU is 2.5GHz. The square root of 2,500,000,000 is 50,000...

Interestingly, both Sublime Text and Atom are two programs that I absolutely cannot use over X11 forwarding without noticeable lag ... Even if the OS and the X server are on the same local machine.

All of this to build 'like' buttons. #cynicism

I know you are joking, but technically this is possible today.


Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact