Re: Quaject-style run-time code synthesis for the Visitor pattern

--===============1024716272==
Content-Type: multipart/alternative; boundary=047d7bdc9bf203c19404de1cec05

--047d7bdc9bf203c19404de1cec05
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: quoted-printable

I made a realtime raytracer a while back and I had good luck with storing
the nodes in an array in depth-first order with skip pointers. You get
great cache coherency and the traversal code is most just incrementing a
pointer. Here's a bit of a description of it:
http://www.cse.chalmers.se/edu/course/_courses_2011/TDA361/EfficiencyIssues=
ForRayTracing.pdf
On Jun 1, 2013 8:58 AM, "Dave Long" <[email protected]> wrote:

> Suppose you want to be able to execute the Visitor pattern as quickly
>> as possible on some tree structure.  You could compile your tree
>> structure into executable code, each node a subroutine which invokes a
>> method of the visitor object =97 traditionally each node type invokes a
>> different method =97 and then passes the visitor object to each child
>> node.
>>
>
> My knee-jerk response is that waiting for i-cache misses is probably not
> much faster than waiting for d-cache misses, and so it's probably better =
to
> spend effort massaging your tree into a serialized form suitable for
> traditional loops; I'd guess that the increased instruction count is easi=
ly
> outweighed by the better prediction and streaming.  What kinds of results
> have you seen?
>
> -Dave
>
> (although if you squint at it properly, doing this kind of thing in
> general is almost exactly what distinguishes compilers from interpreters)
>
> --
> To unsubscribe: http://lists.canonical.org/**mailman/listinfo/kragen-**
> discuss <http://lists.canonical.org/mailman/listinfo/kragen-discuss>
>

--047d7bdc9bf203c19404de1cec05
Content-Type: text/html; charset=windows-1252
Content-Transfer-Encoding: quoted-printable

<p dir=3D"ltr">I made a realtime raytracer a while back and I had good luck=
 with storing the nodes in an array in depth-first order with skip pointers=
. You get great cache coherency and the traversal code is most just increme=
nting a pointer. Here&#39;s a bit of a description of it:<br>

<a href=3D"http://www.cse.chalmers.se/edu/course/_courses_2011/TDA361/Effic=
iencyIssuesForRayTracing.pdf">http://www.cse.chalmers.se/edu/course/_course=
s_2011/TDA361/EfficiencyIssuesForRayTracing.pdf</a></p>
<div class=3D"gmail_quote">On Jun 1, 2013 8:58 AM, &quot;Dave Long&quot; &l=
t;<a href=3D"mailto:[email protected]">[email protected]</a>&gt; wrot=
e:<br type=3D"attribution"><blockquote class=3D"gmail_quote" style=3D"margi=
n:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">
Suppose you want to be able to execute the Visitor pattern as quickly<br>
as possible on some tree structure. =A0You could compile your tree<br>
structure into executable code, each node a subroutine which invokes a<br>
method of the visitor object =97 traditionally each node type invokes a<br>
different method =97 and then passes the visitor object to each child<br>
node.<br>
</blockquote>
<br>
My knee-jerk response is that waiting for i-cache misses is probably not mu=
ch faster than waiting for d-cache misses, and so it&#39;s probably better =
to spend effort massaging your tree into a serialized form suitable for tra=
ditional loops; I&#39;d guess that the increased instruction count is easil=
y outweighed by the better prediction and streaming. =A0What kinds of resul=
ts have you seen?<br>

<br>
-Dave<br>
<br>
(although if you squint at it properly, doing this kind of thing in general=
 is almost exactly what distinguishes compilers from interpreters)<br>
<br>
-- <br>
To unsubscribe: <a href=3D"http://lists.canonical.org/mailman/listinfo/krag=
en-discuss" target=3D"_blank">http://lists.canonical.org/<u></u>mailman/lis=
tinfo/kragen-<u></u>discuss</a><br>
</blockquote></div>

--047d7bdc9bf203c19404de1cec05--

--===============1024716272==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

-- 
To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-discuss
--===============1024716272==--