[L2Ork-dev] [t a] speedup

Jonathan Wilkes 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
> blowup.

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.)

-Jonathan


More information about the L2Ork-dev mailing list