[L2Ork-dev] [t a] speedup
jon.w.wilkes at gmail.com
Thu Apr 5 17:40:58 EDT 2018
On Thu, Apr 5, 2018 at 5:21 PM, Albert Graef <aggraef at gmail.com> wrote:
> On Thu, Apr 5, 2018 at 10:34 PM, Jonathan Wilkes <jon.w.wilkes at gmail.com> wrote:
>> I'm not sure what you mean about quadratic blowup.
> If I understood correctly, you want to just optimize away the trigger
> and connect the wires directly to the targets. But if you have O(n)
> incoming wires
Let's say: 2 incoming
> in a trigger with O(m) outlets,
Let's say: 4 outgoing ([t a a a a])
> you'll get O(nm) direct
> connections in total, right? Take n==m and you get the quadratic
n * m = 8.
For direct connections you iterate over a linked list of t_outconnections
per object. So 2 incoming objects * 1 linked list of four outlets each.
This means you have two calls total to outlet_anything.
For trigger you have a typedmess call for each incoming object, plus
the trigger method invocation. So two typedmess plus method call.
In each method call you have 4 dereferences to t_outlet* (or a deref
to the helper struct that contains the t_outlet*). Not much to that.
But for each iteration of the loop you've got a call to outlet_anything.
Since we have two wires coming to the input of trigger we're triggering
two passes through the array of outlets.
That's eight total calls to outlet_anything
So to recap:
bare wires: 2 outlet_anything calls
trigger: 2 typedmess calls, 2 trigger_anything calls, 8 outlet_anything calls
One caveat: for bare wires we're doing two walks through a linked list
vs. array iteration inside trigger_anything. But any gain you'd get from
array iteration over linked list walk is being swallowed by the function
call overhead. (At least that's what I *think* I'm measuring.)
More information about the L2Ork-dev