site banner

Small-Scale Question Sunday for January 8, 2023

Do you have a dumb question that you're kind of embarrassed to ask in the main thread? Is there something you're just not sure about?

This is your opportunity to ask questions. No question too simple or too silly.

Culture war topics are accepted, and proposals for a better intro post are appreciated.

3
Jump in the discussion.

No email address required.

What's the term for scheduling events in a program loop to avoid constant iteration?

For example: there are objects that get updated every 6000 game ticks after they first appear. Say there are currently 4000 of them. To avoid having 4000 separate timers iterating every tick, they are all on a single array with their id# and time of their next update. The game checks the first item of the array each tick to see if it needs updating. When an object is updated or a new one is created, it gets 6000 ticks added to its update time and moved to the end of the array (or removed if the object had been deleted since its last update).

Is there any way to avoid running the update clock every tick to check if tick# >= next_update_tick# ?

One way to do it would be to have a global tick counter for all similar processes, but it feels like there should be a better way than having the program ask "are we there yet?" every tick for up to 6000 ticks. (Unless you're coding Minecraft, in which case every frog scans every block within jumping range every tick because fuck you.)

Lots of sim games do their update processes on tick multiples: modulo every 5, 10, 100 ticks, etc. That way if you have 50 "every 100 ticks" updates you only need 1 check to see if it's time to run them all, instead of 50.

I guess you could have an array of scheduled updates: if updateX is scheduled for tick 20300, and updateY is scheduled for tick 32000, the global clock just makes one check each tick to see if it's 20300 yet, and if not then it's not 32000 either.

Obviously just the first step got us down from 4000 checks per tick to 1, which is probably more than good enough. But like I said it feels like I'm missing some smarter way of doing this.

If I'm understanding you correctly, which I may not - doing a single comparison-then-branch every "tick" is free and not worth worrying about, unless you're doing millions of ticks per second or something. There isn't really a smarter way because one comparison per tick is nothing compared to billions of instructions per second. As you say you could while(true) { run_100_ticks(); check_timers(); } but I don't see the benefit.

Yeah, that's basically what I'm asking.

When you're doing stuff at scale, avoiding constant checks is pretty important. Factorio saves a ton of update time by putting unused entities to sleep and not having them periodically check if it's time to wake up; they go completely inactive in updates until an active entity connected to them pings them to do something.

When you have 55,000 robot arms not checking if they need to move every tick, the performance savings are measurable.