3 ms·

I found it interesting how concrete Casey gets, and how he quickly identified the cause of the UI bug (+ a mitigation). Meanwhile, it looks like Bob was specula

• comex 4y ago
  But Bob was right that the problem was algorithmic. Checking whether a string ends with a prefix of an emoji abbreviation is a task that could easily be done in a microsecond. It’s apparently taking 100 milliseconds, which is 100,000 times slower. Even factoring in the overhead of JavaScript, you could easily add a 10x or 100x “clean code” penalty and still be nowhere near the level where it’s a performance problem – if the algorithm is correct. By “algorithm” I’m referring to more than just asymptotic complexity. Even so, as for “O(n^2)”… well, I didn’t analyze the code myself, but judging by Casey’s analysis (or even just by the symptoms), it seems quite likely that the time taken to input a character is at least O(n) in the number of characters entered so far (if not worse). That makes the total operation of entering n characters take O(n^2) time. Bob does seem to be referring to the total being O(n^2) rather than each character being O(n^2), since the reallocation strategy he mentioned as an example would similarly take O(n) per character. In that context, O(n^2) is less of a guess, more of a reasonable assumption given the observed performance characteristics. And it’s a reasonable aspect to point a finger at, because lowering the asymptotic complexity would be an essential part of fixing the performance problem. Not sufficient by itself, but pretty much necessary.