Chris Colefax and I were discussing about improvements of the compressed
mesh macros so that they could be easier to maintain and use. He noted that
the parsing of #macros is so slow (specially when #included from an external
file) that he is not using them in many places where speed is needed. This
of course causes some serious problems in modularity and usability.
  Why #macros are so slow specially when #included? Can this be improved?

  Here is a copy of Chris' original response (with his permission):

From cco### [at] geocitiescom Sun Jan  9 18:24:47 2000
Date: Sat, 8 Jan 2000 11:19:22 +1000
From: Chris Colefax <cco### [at] geocitiescom>
To: Nieminen Juha <war### [at] cstutfi>
Subject: Re: A comment about the pcm macro

Warp,

I guess it must seem rather ridiculous to repeat as much macro code as I
have, and while I was writing the latest updates for MeshComp 2.1 I have to
admit I considered simplifying the mesh creation macros in just the way you
describe.

However, there is actually a reason I wrote the macros as I did -
performance.  In every situation I've tested (various OS's, file caching
on/off) macros parse considerably slower when called in a loop from an
include file as opposed to defining the macro in the same POV file as it is
called from, or (fastest of all) placing the code to be executed directly
within the loop.

A simple example:

   #macro M () #declare C = C + 1; #end
   #declare C = 0; #while (C < 10000) M () #end

On my machine, saved and run from a single file this code takes about twice
as long as incrementing the counter directly without a macro.   Placing the
macro into an included file runs about 7-8 times slower again (ie. 14-16
times as slow as not using the macro!).

Personally I felt it was worth sacrificing simplicity for speed, particuarly
considering how the mesh creation macros might be used.  There may well be a
case for allowing both options, so that users who want to quickly write a
mesh creation macro for, say, a still scene can do so without worrying about
the full coding.  And maybe raising the above parsing performance issues in
povray.programming could lead to a patch that eliminates speed concerns
altogether (hint, hint!)?

Yours,

Chris.

---------------------
>   I examined yur pcm.mcr and noticed one thing that might be done better.
>   I don't want to preach you about programming guidelines or modularity or
> anything like that, but I noticed that the code to read the pcm data is
> copied several times in the file (each mesh creation macro has the same
> code copied).
>   This, as you probably know, is not a good idea. If you have to make a
> change to the code, you have to do it many times with the risk that you
> don't make the change properly in every place. It also requires lots of
> work to maintain this (it can be specially seen with the new PCM3
support).
>   But the most important thing is that it makes it difficult for the user
> to make his own mesh creation macros. The user must copy the same
(lengthy)
> code each time he wants the make a mesh creation macro.
>   I think that there should be a set of macros which can be used to more
> easyly read the mesh data. The logics of the mesh decompression should be
> completely hidden inside these macros; the only thing that the macros
should
> do is the "gimme the next triangle, please"-functionality.
>   Doing it this way will save you and the user lots of trouble and work.
> It will make it easier to you to modify the code and add new functionality
> and it will also make it a lot easier for the user to make his own macros.
> The user wouldn't even have to worry about what type of input file is he
> reading (PCM1 or PCM3) because the reading macros would hide that
unnecesary
> information inside them.
>   In an optimal case, if in the future we add some new type of triangle
> mesh format (e.g. PCM4), the only modifications needed could be done in
> the reading macros and the mesh creation macros could be left untouched.
> It would also save lots of work since the modifications had to be made
only
> in one place (instead of having to modify lots of mesh creation macros).
> Also all the user-made mesh creation macros would work as-is, without
> modification, with the new format.




-- 
main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
):5;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/

Post a reply to this message

In article <3878b696@news.povray.org> , Nieminen Juha 
<war### [at] punarastascstutfi>  wrote:

> Chris Colefax and I were discussing about improvements of the compressed mesh
> macros so that they could be easier to maintain and use. He noted that the
> parsing of #macros is so slow (specially when #included from an external file)
> that he is not using them in many places where speed is needed. This of course
> causes some serious problems in modularity and usability.

It is possible to improve the speed of macros, but it requires quite a few
changes if it is done right.

> Why #macros are so slow specially when #included?

This is the easiest question to answer. The key problem is in Invoke_Macro
and Return_From_Macro. When a macro is in another file POV-Ray opens and
closes that file _each_ time the macro is invoked. It not only does that,
but it also uses Locate_file to search for it each time (usually by trying
to open it in each directory). So first, if it is not in the first directory
POV-Ray searches for, this will waste some time. Now, when parsing the macro
is done, it will close the file again.

> Can this be improved?

There are several ways which when combined should give much better results.
The worst idea would be to leave all files with macros open as different
systems have different limits for the maximum number of open files. So a
compromise would be to cache for example the ten most frequently opened
files. This would probably give some improvement.

It could be even faster if frequently used parts of all files would also be
cached dynamically, at least for systems that don't offer a good disk cache.

It might also be worth looking into the symbol table stuff going on in there
in order to support local variables, but I don't know exactly how that part
of the code works.


       Thorsten


____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message

Thorsten Froehlich <tho### [at] trfde> wrote:
: When a macro is in another file POV-Ray opens and
: closes that file _each_ time the macro is invoked.

  This sounds crazy!

  Why can't macros be loaded into memory (even as-is, or in a bytecode format)
and parsed there? I think this would improve the speed a lot.

-- 
main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
):5;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/

Post a reply to this message

In article <3879e1a2@news.povray.org> , Nieminen Juha 
<war### [at] punarastascstutfi>  wrote:

>   This sounds crazy!

I know. It is not the best implementation, but with the current POV-ray it
is the best and most compatible one possible. Any better implementation
would likely require a lot of changes to the parser.

>   Why can't macros be loaded into memory (even as-is, or in a bytecode format)
> and parsed there? I think this would improve the speed a lot.

Yes, maybe for 4.0. Who knows :-)


     Thorsten

Post a reply to this message

> Personally I felt it was worth sacrificing simplicity for speed, particuarly
> considering how the mesh creation macros might be used.  There may well be a
> case for allowing both options, so that users who want to quickly write a
> mesh creation macro for, say, a still scene can do so without worrying about
> the full coding.  And maybe raising the above parsing performance issues in
> povray.programming could lead to a patch that eliminates speed concerns
> altogether (hint, hint!)?

God save me, but I'm working on it.  At the moment it seems to be
executing properly.  I need to clean up the code and test it in various
alignments, but it was possible with minimal code involvement.

In my Linux, the example that Chris gave is only marginally faster when
the macro is hand-expanded.  Afterwards, I don't notice any difference
at all.

I should be satisfied in a few hours that it works properly and will put
a patch somewhere.  As I don't run any patched POV-Ray, I don't know how
well it will merge with them!

Post a reply to this message

I have placed the patch at:
http://www.pacificcoast.net/~loth/povray-macro-patch.gz

Standard disclaimers apply; I don't actually have much of an idea how
the parser works yet, but I can ape the knowledge well.  As long as
reality continues its structural integrity it should work, as there are
no places where it knows how to not work.

What is the etiquette for these patches -- could I post it in
povray.binaries.programming and announce it here, or post it here? 
Should it be gzipped or unzipped for review?

In general, I don't see much of a difference in speed, about a 5% gain. 
When I put the #while loop in a macro, though, I got a 11% gain, since
the string's fseek is naturally faster.  Now that's the way macroes
should be!  Also, when going through an included macro, it's three times
faster.  Chris should note extreme speed increases.

Trivial but fun.

Post a reply to this message

>Trivial but fun.

You place little importance on your work. Bad boy. Thanks for making this
great program better. You've just save us many hours of parsing. I am in
debt to you. =)

Post a reply to this message

"Burton Radons" <lot### [at] pacificcoastnet> wrote in message
news:388### [at] pacificcoastnet...
> I have placed the patch at:
> http://www.pacificcoast.net/~loth/povray-macro-patch.gz
>
> What is the etiquette for these patches -- could I post it in
> povray.binaries.programming and announce it here, or post it here?
> Should it be gzipped or unzipped for review?
>

Sounds about right to me anyway, pov patch binaries in p.b.p. (guessing "other"
patches don't apply but nothings mentioned at p.f-a-q.) and announced in p.p.
should be best.  I've had trouble getting a gz file to extract and I've also
heard others have the same problem.  I used to use WinZIP but it didn't work on
some of those and now use ZIP Magic which says it can but I've had the same
problem.  Actually my guess is they were always bad downloads for one reason or
another, or maybe just compressed in an unsupported way.

Bob

Post a reply to this message

Attached is a further patch to make it behave properly in strange
situations.  The masking out of ok_to_declare in that point is a hack,
but a harmless one, I think.  Also, it was not responding well to errors
and I've plugged those two holes.  Finally, there was a memory leak of 8
bytes for every macro call.  Apologies.

Post a reply to this message

Attachments:
Download 'us-ascii' (2 KB)

Burton Radons <lot### [at] pacificcoastnet> wrote...
> In general, I don't see much of a difference in speed, about a 5% gain.
> When I put the #while loop in a macro, though, I got a 11% gain, since
> the string's fseek is naturally faster.  Now that's the way macroes
> should be!  Also, when going through an included macro, it's three times
> faster.  Chris should note extreme speed increases.

Burton,

I've adapted your patch (including the update) to MegaPov.  I had to make a
few modifications.  For example, that fread that you mentioned was probably
not platform independent had to be ditched due to CR+LF in the dos/win
environment.

I also have a few ideas about further abstraction of the Data_File struct
(you should have constructors and destructors, IMHO).

Anyway, in Windows this makes a big difference in speed.  As a test, I
rendered "pyramid.pov" (part of the official distribution).  At a recursion
depth of 6, it parsed in 85 seconds in the official 3.1g version, and only
46 seconds in MegaPov.

Then, I modified pyramid.pov so that the creation of the sphere was placed
in a one-line macro in a separate INC file.  Doing it this way led to a
parse time of 260 seconds (4min 20sec) in 3.1g and only 53 seconds in
MegaPov.  :-)  Granted, I intentionally created a macro in a separate file
that would be called very many times from the original file (basically the
worst-case scenario for the official version), but still....

Thanks for your contribution!

-Nathan

Post a reply to this message