5 ms·

A classic example of diminishing marginal returns.

hinkley 3y ago
Toy solutions deal with small data inputs. How many lines of that 20k is just optimizing for large inputs (you can’t have long repeating sections in small inputs).
- jhp123 3y ago
  I've written a linear-time regex matcher in 65 lines of code: https://jasonhpriestley.com/regex https://jasonhpriestley.com/regex
  - vidarh 3y ago
    That's beautiful. And I think a great illustration of how much more impactful the "next n lines" or so are going to be than the "last n lines" EDIT: Also, the impact is even greater when looking at your performance improvements with the dfa conversion as well: https://jasonhpriestley.com/regex-dfa https://jasonhpriestley.com/regex-dfa
  - saberience 3y ago
    What features does it support? What if I pass in a complex regexp with data several GB in size? There is a large difference between toy examples and hardened enterprise ready code.
    - vidarh 3y ago
      The features are less important than the linear complexity. It lowers to an NFA. An NFA can recognise any linear language, so adding more features affects the generation of the NFA, while increasing the performance involves faster matching against the NFA. In this case he's done a followup with benchmarks where he's converting the NFA to a DFA ajd comparing favourably against both Node and your browers regexp engine with only a tiny little bit extra code: https://jasonhpriestley.com/regex-dfa https://jasonhpriestley.com/regex-dfa That doesn't mean there isn't value to the rest of those 20k lines of code I referenced - that was not the point. A lot of them adds a bunch of convenience, like a more expressive syntax that saves you from writing more convoluted regexps, and it presumably bought more performance than their previous, smaller iteration, every step up from a much smaller engine way back. I'm sure one could do better with less, but I'm also not dismissing that I'm sure each step was reasonable given the constraints. But that too is also not the point. It was not about dismissing the size of the Ruby regexp engine as not worth it. The point was that there is a very significant and rapid diminishing return, and that this explains why you can do so seemingly much with so very little, because the leap from no capability to something usable takes very little, but each subsequent increment will tend to buy you less, for more work. That doesn't mean people should stop putting in that extra work and squeeze out a bit more. It just gives an answer to the question in the link.
      - nine_k 3y ago
        Being O(n) is important, but the size of the constant factor is important, too. E.g. the theoretically most efficient known matrix multiplication algorithm only outperforms the less efficient common algorithms at ludicrous matrix sizes, because of the huge constant factor.
        vidarh 3y ago
        Yes, but this is again totally besides the point, and addressed by the second link to the version that does dfa conversion in a few dozen more lines and is competitive with the regexp implementation in chrome.
  - hinkley 3y ago
    I think this is a good base case for exploring how achieving feature parity affects the code.
- vidarh 3y ago
  A lot of it is, but the point remains no matter where you set t he bar, you can usually get most of the benefit with a tiny portion of the code. Sometimes squeezing out a tiny bit more performance isn't worth much, sometimes it's worth 10x or 100x the amount of code - the point is not that it's inherently wrong to write all that extra code. But you should at least be aware when the returns are diminishing to a point where the payoff becomes uncertain.
  - pixl97 3y ago
    Dealing with edge cases is where your code blows up. Once you find an edge case do you leave it unaddressed and the program generate a wrong/unexpected answer? Could it be a potential security flaw? Unfortunately when we write initial specifications we almost certainly get them wrong in one way or another. Trying to deal with that after the fact commonly leads to application bloat.
    - fiddlerwoaroof 3y ago
      I think the most important thing to ask about an edge case is “how could I have designed this code to make it not an edge case”
      - pixl97 3y ago
        "I should have beat the customer until they gave me full specifications of what they needed before writing code" Is unfortunately what happens a lot.
        vidarh 3y ago
        Ah, but retrospectively what matters more is instead "now that we know how bad that got, how can we use what we learnt to do better when we rewrite". It's not a given that it's a bad thing to allow customers to drive rapid iteration even when it leads to a mess, as long as you're prepared to take the consequences. A lot of the worst systems I've seen were systems where people resisted rewrites rather than plan for them, often because they didn't establish enough tests, and/or were upset over the sunk costs. Treating the first iteration or iterations as throwaway learning experiences can be useful. If you plan for that from the start you can allow yourself to take shortcuts you otherwise wouldn't (but you sure as hell better make sure management understands sticking to that throwaway version isn't an option), knowing the lessons learnt will feed straight into the next iteration (and of course building a throwaway system doesn't mean every part needs to be written to be ditched).
- rurban 3y ago
  My tiny regex in C is complete, in 1K of C. With formal verification https://github.com/rurban/tiny-regex-c/blob/master/re.c https://github.com/rurban/tiny-regex-c/blob/master/re.c
RetroTechie 3y ago
It does make one wonder why adding diminishing returns is the usual way of software development. Proof of concept -> early release -> stable release -> add feature -> add feature -> add feature, ..., repeat. CPU cycles, RAM use, storage space, bugs, updates, managing complexity, manuals, adapting to newer standards, programmers understanding codebases, etc, etc, etc. It's not like incremental additions are 0-cost. Kind of like inventory: of all the stuff (most) people have in their homes, only a small fraction is used regularly. The rest only sees use very rarely, or exists for "nice to have", decoration, or plain luggage / junk. Turning free living space into a junk bin, making it more difficult to move house, etc. People who think that junk in their attic costs nothing, can't do math. The software fix would be to hunt aggressively for ways to simplify, reduce binary size & in-use memory footprint, remove lesser-used features, weigh any feature (present or potentially added) vs. its impact on maintainability, code size, etc. In other words: maximize the bang-per-byte. Note this does NOT need to mean "feauture starved". Just very capable / useful given its footprint. As opposed to maximize the feature list, or throw complex algorithms to squeeze every last % of performance. Any projects out there that have bang-per-byte as #1 priority?
- vidarh 3y ago
  I've come to think we really should be more comfortable forking projects and keeping them small vs. adding features. E.g. consider the space of tiny to small-ish X11 menu tools. There's ratmenu, 9menu, dmenu, rofi, roughly ranged from tiny to slightly on the larger side, and I'm sure many more. If I want to add features to 9menu or ratmenu, I wouldn't add features directly to them unless it's something really minor or very generic. I'd fork them, or rewrite from scratch. Their appeal is that they're small and focused. I'd rather have a choice of a dozen like them with slightly different feature sets that are easy to customize and tweak for my use, than one big one. Where the cutoff point is varies - I tend to find rofi a bit too big and complex, for example.

Toy solutions deal with small data inputs. How many lines of that 20k is just optimizing for large inputs (you can’t have long repeating sections in small inputs).

jhp123 3y ago
I've written a linear-time regex matcher in 65 lines of code: https://jasonhpriestley.com/regex https://jasonhpriestley.com/regex
- vidarh 3y ago
  That's beautiful. And I think a great illustration of how much more impactful the "next n lines" or so are going to be than the "last n lines" EDIT: Also, the impact is even greater when looking at your performance improvements with the dfa conversion as well: https://jasonhpriestley.com/regex-dfa https://jasonhpriestley.com/regex-dfa
- saberience 3y ago
  What features does it support? What if I pass in a complex regexp with data several GB in size? There is a large difference between toy examples and hardened enterprise ready code.
  - vidarh 3y ago
    The features are less important than the linear complexity. It lowers to an NFA. An NFA can recognise any linear language, so adding more features affects the generation of the NFA, while increasing the performance involves faster matching against the NFA. In this case he's done a followup with benchmarks where he's converting the NFA to a DFA ajd comparing favourably against both Node and your browers regexp engine with only a tiny little bit extra code: https://jasonhpriestley.com/regex-dfa https://jasonhpriestley.com/regex-dfa That doesn't mean there isn't value to the rest of those 20k lines of code I referenced - that was not the point. A lot of them adds a bunch of convenience, like a more expressive syntax that saves you from writing more convoluted regexps, and it presumably bought more performance than their previous, smaller iteration, every step up from a much smaller engine way back. I'm sure one could do better with less, but I'm also not dismissing that I'm sure each step was reasonable given the constraints. But that too is also not the point. It was not about dismissing the size of the Ruby regexp engine as not worth it. The point was that there is a very significant and rapid diminishing return, and that this explains why you can do so seemingly much with so very little, because the leap from no capability to something usable takes very little, but each subsequent increment will tend to buy you less, for more work. That doesn't mean people should stop putting in that extra work and squeeze out a bit more. It just gives an answer to the question in the link.
    - nine_k 3y ago
      Being O(n) is important, but the size of the constant factor is important, too. E.g. the theoretically most efficient known matrix multiplication algorithm only outperforms the less efficient common algorithms at ludicrous matrix sizes, because of the huge constant factor.
      - vidarh 3y ago
        Yes, but this is again totally besides the point, and addressed by the second link to the version that does dfa conversion in a few dozen more lines and is competitive with the regexp implementation in chrome.
- hinkley 3y ago
  I think this is a good base case for exploring how achieving feature parity affects the code.
vidarh 3y ago
A lot of it is, but the point remains no matter where you set t he bar, you can usually get most of the benefit with a tiny portion of the code. Sometimes squeezing out a tiny bit more performance isn't worth much, sometimes it's worth 10x or 100x the amount of code - the point is not that it's inherently wrong to write all that extra code. But you should at least be aware when the returns are diminishing to a point where the payoff becomes uncertain.
- pixl97 3y ago
  Dealing with edge cases is where your code blows up. Once you find an edge case do you leave it unaddressed and the program generate a wrong/unexpected answer? Could it be a potential security flaw? Unfortunately when we write initial specifications we almost certainly get them wrong in one way or another. Trying to deal with that after the fact commonly leads to application bloat.
  - fiddlerwoaroof 3y ago
    I think the most important thing to ask about an edge case is “how could I have designed this code to make it not an edge case”
    - pixl97 3y ago
      "I should have beat the customer until they gave me full specifications of what they needed before writing code" Is unfortunately what happens a lot.
      - vidarh 3y ago
        Ah, but retrospectively what matters more is instead "now that we know how bad that got, how can we use what we learnt to do better when we rewrite". It's not a given that it's a bad thing to allow customers to drive rapid iteration even when it leads to a mess, as long as you're prepared to take the consequences. A lot of the worst systems I've seen were systems where people resisted rewrites rather than plan for them, often because they didn't establish enough tests, and/or were upset over the sunk costs. Treating the first iteration or iterations as throwaway learning experiences can be useful. If you plan for that from the start you can allow yourself to take shortcuts you otherwise wouldn't (but you sure as hell better make sure management understands sticking to that throwaway version isn't an option), knowing the lessons learnt will feed straight into the next iteration (and of course building a throwaway system doesn't mean every part needs to be written to be ditched).
rurban 3y ago
My tiny regex in C is complete, in 1K of C. With formal verification https://github.com/rurban/tiny-regex-c/blob/master/re.c https://github.com/rurban/tiny-regex-c/blob/master/re.c

RetroTechie 3y ago

It does make one wonder why adding diminishing returns is the usual way of software development. Proof of concept -> early release -> stable release -> add feature -> add feature -> add feature, ..., repeat. CPU cycles, RAM use, storage space, bugs, updates, managing complexity, manuals, adapting to newer standards, programmers understanding codebases, etc, etc, etc. It's not like incremental additions are 0-cost. Kind of like inventory: of all the stuff (most) people have in their homes, only a small fraction is used regularly. The rest only sees use very rarely, or exists for "nice to have", decoration, or plain luggage / junk. Turning free living space into a junk bin, making it more difficult to move house, etc. People who think that junk in their attic costs nothing, can't do math. The software fix would be to hunt aggressively for ways to simplify, reduce binary size & in-use memory footprint, remove lesser-used features, weigh any feature (present or potentially added) vs. its impact on maintainability, code size, etc. In other words: maximize the bang-per-byte. Note this does NOT need to mean "feauture starved". Just very capable / useful given its footprint. As opposed to maximize the feature list, or throw complex algorithms to squeeze every last % of performance. Any projects out there that have bang-per-byte as #1 priority?

vidarh 3y ago
I've come to think we really should be more comfortable forking projects and keeping them small vs. adding features. E.g. consider the space of tiny to small-ish X11 menu tools. There's ratmenu, 9menu, dmenu, rofi, roughly ranged from tiny to slightly on the larger side, and I'm sure many more. If I want to add features to 9menu or ratmenu, I wouldn't add features directly to them unless it's something really minor or very generic. I'd fork them, or rewrite from scratch. Their appeal is that they're small and focused. I'd rather have a choice of a dozen like them with slightly different feature sets that are easy to customize and tweak for my use, than one big one. Where the cutoff point is varies - I tend to find rofi a bit too big and complex, for example.