25

Yesterday found an error in my algorithm that caused it go o(n^n) instead of o(1). Feels so goddamn good!
How was your day?

Comments
  • 3
    Please tell more, if you can
  • 2
    I'm also interested
  • 2
    😮 That's a real performance improvement
  • 2
    @korrat @gitpush Ok, the n^n was a bit clickbaity when I think about it. I had a nested loop iterating over a file, and instead of terminating it when condition was met, I terminated only the inner part. An obvious mistake when you think about it but I couldn't catch it for a while (I didn't quite know what caused the slow-down). So yeah...
  • 5
    Nice. I've had similar things. One was three nested loops iterating over coordinates in a box.

    Now once upon a time when this was built the only iteration happened along a single dimension, so the break actually did its job of stopping the whole computation.

    Then the two outer loops were added and the break was not that useful anymore. But the function worked correctly, so whatever.

    When problem sizes grew, people started noticing performance problems. Time to optimize!

    But first I wrote a benchmark that I thought mirrored the problematic function. No performance problems. Even increasing the problem size did not affect performance that much.

    I kept checking the benchmark, thinking I must have done something wrong. When I gave up and as a last resort copied over part of the function, git marked the file as changed. The diff: one line. My benchmark used to have a return instead of the break...
Add Comment