in reply to Re^3: Some code optimization
in thread Some code optimization

Thank you, I will look into it. But I think the problem starts with the first problematic function (as the name suggests :)) - gene_to_legal_range.

When I next just before it I run 6 times faster than if I next just after it (~4 seconds compared to ~27 seconds for 50 iterations). This subroutine really looks simple to me, so I don't see why it has to take so much time (subroutine overhead?!).

p.s. I now run my home PC and the benchmarking results are a little different (but the relative differences are similar).

UPDATE

Almost always the sort is done on an array with a single element (there are cases where there are more). I even tried removing the sort at all, just to see the effect on running time - there is no change.

But, again, I suggest we start with the first, more simple subroutine. Is it really just perl subroutine overhead? Is there anything I can do about it?

Replies are listed 'Best First'.
Re^5: Some code optimization
by graff (Chancellor) on Jun 18, 2010 at 09:46 UTC
    I think the problem starts with the first problematic function...

    Now you aren't making sense. According to your initial description of timing relations: 

    65 sec for full code
15 sec for code MINUS "is_contained()" call (2nd "next" uncommented)

    [download]
    That really makes it look like "is_contained()" accounts for most of the run time, which I would expect, since that is the part that involves several more layers of function calls, with lots of min, max, sort, grep, etc going on (some of it obviously not needed). "Look into it", for sure.

    To reiterate the question in my update: is there a way to move the sorting out of the innermost loop? E.g. might there be an appropriate "sort" on one or both of the lists that drive the two "foreach" loops in "scenario()", which would simplify operations inside the inner loop? Can anything be done as part of the outer foreach so that you don't have to do it repeatedly as part of the inner loop?

[reply]
[d/l]

      "is_contained()" indeed accounts for most of the run time, but "gene_to_legal_range()" is also much slower than I would expect.

      Updated benchmarks (tested again with the original posted code):
      - Both subroutines executed: ~64 seconds
      - Only "gene_to_legal_range()" is executed: ~15 seconds
      - Only "gene_to_legal_range()" is executed but its body replaced with just a return: ~6.1 seconds
      - none is executed: ~4.5 seconds

      So "gene_to_legal_range()", which is quite simple, triples the run time (15 vs 4.5). Also just calling this subroutine, even if it does nothing (just a return) adds some significant time (6.1 vs 4.5).

      In the final program I will have ~1000 iterations (instead of 50) so these differences do matter.

      To conclude, I agree that "is_contained()" consumes more time, but I suggest that we first assert that the first, much simpler function is "optimal" Since I'm new to perl optimization, this might also help me know what to expect, what is considered OK (e.g. such an overhead for a subroutine call?) and what is not.

      UPDATE: and as for sort, again, I removed it completely. Got ~60 seconds (instead of ~64). But I again suggest we first "clear" with the first, simpler sub.

[reply]
[d/l]
[select]
        To conclude, I agree that "is_contained()" consumes more time, but I suggest that we first assert that the first, much simpler function is "optimal"

        Suit yourself, but to me your statement is a clear example of misplaced priorities, bordering on irrational obsession. The few changes I suggested save an amount of time equal to the total consumed by that first function.

        Since I'm new to perl optimization...

        ... or to optimization in general? If you want to focus on optimizing that first function, you should be coding it in C (and that'll be a waste of time if you don't fix the second function, and/or move stuff from inner to outer loops, or just work out a better approach from first principles).

        UPDATE: BTW, did you happen to try moving the logic of that first function into the caller? (ie. do that stuff in-line in "scenario()" rather than as a sub call to "gene_to_legal_range") -- that might trim your 16 sec. test case down to 13 (about 20%, which is respectable).

[reply]

In Section Seekers of Perl Wisdom