Deep recursion in Tk repeat

[polypompholyx]

Hello Monks,

I have mostly finished writing a Tk composite widget that simulates a biological movement called taxis, so that the technicians at the school I work at don't have to collect two thousand woodlice (sowbugs) for a biology practical next month. The module sets up a Canvas full of Photos of woodlice that mill about according to certain rules, and eventually end up mostly on the right hand (dark) side of the canvas.

The simulation script uses a hand-rolled event-loop to call the taxis method, which moves the woodlice through one cycle. However, this...

while (1)
{
  $taxis->taxis(); # move every woodlouse through one cycle
  DoOneEvent( $running ? DONT_WAIT : ALL_EVENTS );
}

didn't work quite right, because the loop (hence the simulation) ran much faster if taxis only had to move one woodlouse, and much slower if it tried to animate fifty at a time. As an alternative, I have tried...

$mw->repeat( 50, [ sub { $taxis->taxis() if $running } ] );
DoOneEvent( $running ? DONT_WAIT : ALL_EVENTS ) while 1;

which does what I want, but if the refresh rate (50 ms) is reduced to e.g. 20 ms with a large population of woodlice, the script hangs and complains of deep recursion, presumably because it takes longer than 20 ms to run the taxis code.

This is probably OK, as 50 ms isn't too jerky, but I am a little worried about the elderly computers at the school hanging with values of population and refresh rate that work fine on my speedier machine. I can easily hard-code a slower refresh rate if this happens, but I wondered if there was a nicer way of guesstimating a suitable refresh rate. I guess it would be a combination of benchmarking the code, getting the processor speed somehow, and working out something empirically. Does this sound reasonable, does anyone have any idea how to get information on the 'speed' of the computer, is there a better way to code the refresh callback, or am I just worrying unnecessarily?

Any advice gratefully received!

polypompholyx

[bbfu]

the loop (hence the simulation) ran much faster if taxis only had to move one woodlouse, and much slower if it tried to animate fifty at a time.

Huh. Makes sense to me. You're making the program do a lot more work when there's 50 lice, so you have to expect that it will take longer.

What happens when you set up the repeat is that, as soon as the 50ms is up, you start back at the begining of the list of lice (by recursing into the repeat via an update() or DoOneEvent()), even if you never finished moving the later lice. This allows the lice at the begining of the list to keep moving, while the later lice never get to move at all. And, of course, as this process continues ever deeper, you end up with a "deep recursion" error.

You have to face the fact that it will take longer to move all the lice on a slower computer. The computer you're using can apparently move all 50 lice within 50ms but not within 20ms. A slower computer may take 70ms to move them all.

Your original loop (without using repeat) will always move every lice in as little time as possible. You can always slow it down, if you want, but there's no way (except for possibly optimizing the display or movement routines) to make it go faster.

If you want to enforce some maximum frame rate (aka, a minimum amount of time to spend during each refresh), you maybe using something along the lines that benn suggested or, perhaps more simply:

use constant MIN_REFRESH => 0.02; # 20 ms
while(1) {
  my $start = Time::HiRes::time;
  $taxis->taxis() if $running;
  DoOneEvent() until Time::HiRes::time-$start > MIN_REFRESH;
}

This will run through all the lice each time, without recursion, and will always take at least 20ms to do so, though it may take (much) longer, if it needs to.

bbfu
Black flowers blossom
Fearless on my breath

[polypompholyx]

Thanks: idling away some slack time if taxis returns too quickly seems to do the trick. I knew the sim would take longer with larger numbers of lice, the problem was mostly that with a small population and the simple while loop, the lice looked like they were on amphetamines! The only change I have made is to use...

DoOneEvent( DONT_WAIT ) until Time::HiRes::time-$start > MIN_REFRESH;

Since DoOneEvent() alone frequently takes longer than 20 ms to return, and therefore the sim gets very jerky with small populations.

Thanks again!

[benn]

Rather than attempting to guess the refresh rate beforehand, you could work it out at runtime, then use this to drive your main loop - something roughly like...(untested, obviously)

use Time::Hires;
$avg_num=10; # or whatever
$s=time();   #Time::Hires floating-point drop-in
$taxis->taxis() for (0..$avg_num);
$refresh = (time()-$s)/$avg_num;
$refresh = $sensible if ($refresh < $sensible;}

while(1) {
  $start=time();
  $taxis->taxis();
  do { 
     DoOneEvent( $running ? DONT_WAIT : ALL_EVENTS );
  }
  until (time()-$start > $refresh);
}

Cheers, Ben.

[aquarium]

you should only call refresh once per cycle, be the cycle made of 1 movement of a louse or 50000 lice. haven't touched tk for a long time, so can't give you code unfortunatelly.

[bobn]

I'm not sure I understand your code, but why not just arrange for $taxis->taxis to immediately return if another instance is already running?

my $RUNNING = 0;
$mw->repeat( 50 => sub { $taxis->taxis(\$RUNNING) unless $RUNNING} ];
MainLoop;

package taxis;
sub taxis
{
   my ($self, $r_running, @whatever, ) = @_;
   $mw->update;   
   $$r_running = 1;
   # do other stuff that takes a while
   $$r_running = 0;
   return;
}

Of course, this must be modified if $taxis->taxis is recursive.

sub taxis
{
   my ($self, $r_running, @whatever, ) = @_;
   $mw->update;   
   $$r_running = 1;
   # other stuff
   my $null = 0;
   $self->taxis(\$null, $whatever); 
   $$r_running = 0;
   return;
}

....I think.....
--Bob Niederman, http://bob-n.com

All code given here is UNTESTED unless otherwise stated.