Push Instruction Documentation

Orientation
21

exec_do_range is also taking more time than all selection and variation combined.

3 Likes
22

Now that I think about it, is this a little weird? Even if exec_y and exec_do_range are running tons of times because they appear in a bunch of programs and run a lot, shouldn’t each individual execution be short? Does your profiler show you how many times each function is called, or alternatively how long each runs on average, and if so, is the average time higher than other instructions, or is it about the same and they’re just getting called a lot more often?

1 Like
23

Good questions. I did 1 run of substitution-cipher with a population of 500 and 30 generations using 200 training cases and a step limit of 500. exec_do_range seemed less prevalent here than in some of the other runs I have done in the past, but it still shows the comparison.

  • Whole run took 4320 seconds
    • 1.5% of which was doing exec_do_range.
  • exec_do_range was called 5.5 million times.
    • Average of 1.8 calls per program execution.
    • 1.5% of the runtime.
    • Time spent in instruction, not including sub-functions
      • Total 19.51s, Average per call 3.519e-06s
    • Time spent in instruction, including sub-functions
      • Total 63.45, Average per call 1.144e-05s
  • There were 10,697,946 calls to the shove_* instructions (all types reported together).
    • Average of 3.5 calls per program execution.
    • 0.73% of the runtime.
    • Time spent in instruction, not including sub-functions
      • Total 13.51s, Average per call 1.263e-06s
    • Time spent in instruction, including sub-functions
      • Total 31.48, Average per call 2.942e-06s
  • exec_when was called 2.1 million times.
    • Average of 0.7 calls per program execution.
    • 0.04% of the runtime
    • Time spent in instruction, not including sub-functions
      • Total 0.9964s, Average per call 4.664e-07s
    • Time spent in instruction, including sub-functions
      • Total 1.938, Average per call 9.073e-07s

These stats imply the issue is somewhat about exec_do_range being called a lot (which is backed up by the fact that when I lower the step limit time spent in exec_do_range drops proportionally) but also that exec_do_range is one of the most expensive instructions to call a single time.

The breakdown of time spent in exec_do_range is:

  • 40% direct logic of exec_do_range (comparing loop counters, building next iteration, etc.)
  • 20% looking up stack from state
  • 15% enforcing limits when pushing to stack.
  • 15% Peaking at top stack item
  • 10% manipulating the stack.

This gives me a few threads to pull on.

2 Likes
24

I mean, unless there is something super weird about the implementation that is hard to see, the reason exec_do_range runs often is almost certainly about how integer constants arise, not the instruction itself. It’s re-pushed to the :exec stack once for ever integer between the to popped from the stack originally. And in my experience, integers get big very quickly.

Long ago in the earliest days of the Klapaucius fork, the fact that :integer values are so huge just via fiddling led me to force iteration and other bounds that want to be “modest” to use values mod 1000 or 100, internally. I think I named it :exec_do_some at that point? I can’t recall.

Further, if exec_do_range executes code that modifies its own bounds, it’s basically just sparkling exec_y at that point.

2 Likes
25

True, but the average time per call of exec_do_range is 3-10x larger than any other instruction I looked at. In the case of pyshgp, it seems like this is primarily because exec_do_range has to instantiate a few objects and collections to create the block of code that needs to be pushed to the exec stack.

1 Like
26

I did 1 run of GCD with a population size of 500 for 10 generations and 200 training cases. Results are even more dramatic than the previous example.

  • Whole run took 3390 seconds
  • exec_do_range was called 23.5 million times.
    • Average of 23 calls per program execution.
    • 12.55% of the runtime.
    • Time spent in instruction, not including sub-functions
      • Total 104s, Average per call 4.424e-06s
    • Time spent in instruction, including sub-functions
      • Total 425.7s, Average per call 1.811e-05s
  • There were 5.9 million calls to yank_* instructions (all types reported together).
    • Average of 6 calls per program execution
      • 1.2% of the runtime
    • Time spent in instruction, not including sub-functions
      • Total 14.62s, Average per call 2.452e-06s
    • Time spent in instruction, including sub-functions
      • Total 41.4s, Average per call 6.942e-06s

In this run, each call to exec_do_range took 3x the time compared to a simple yank_ instruction. Also, exec_do_range was called 4X more frequently than all three yank_ instructions in the genetic sources combined.

2 Likes