When doing an animation with the new MegaPOV Plus, I sometimes get an "Out
of memory" error. It seems to happen at random with something like 10% of
the frames, and these frames are no different from the frames that doesn't
produce errors.

One strange thing is that in the error messages =, !=, and possible other
characters are always replaced with square characters (). Also, the errors
seem to be always have something to do with the = character. Could this be
related to the #set patch (which I did not use in my scene file)?

By the way, I'm using the windows version MegaPov 0.5a Plus mod 0.3.0.

Greetings,

Rune
--
\ Include files, tutorials, 3D images, raytracing jokes,
/ The POV Desktop Theme, and The POV-Ray Logo Contest can
\ all be found at http://rsj.mobilixnet.dk (updated July 23)
/ Also visit http://www.povrayusers.org

Post a reply to this message

In article <39b57a67@news.povray.org>, "Rune" <run### [at] inamecom> 
wrote:

> When doing an animation with the new MegaPOV Plus, I sometimes get an 
> "Out of memory" error. It seems to happen at random with something 
> like 10% of the frames, and these frames are no different from the 
> frames that doesn't produce errors.

Probably a memory leak, if you start over from the frame that caused the 
trouble, things should work fine(until it runs out of memory again). I 
wish I had some software for tracking down memory leaks...


> One strange thing is that in the error messages =, !=, and possible 
> other characters are always replaced with square characters (). 
> Also, the errors seem to be always have something to do with the = 
> character. Could this be related to the #set patch (which I did not 
> use in my scene file)?

This is very strange...I don't see how it could be related to the set 
patch...unless my experiments with getting the "# VarName" syntax to 
work got in there by accident. I will check, this is the most likely 
explanation for what is going wrong.

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message

In article <chrishuff-C86F26.19092605092000@news.povray.org>, Chris 
Huff <chr### [at] maccom> wrote:

> This is very strange...I don't see how it could be related to the set 
> patch...unless my experiments with getting the "# VarName" syntax to 
> work got in there by accident. I will check, this is the most likely 
> explanation for what is going wrong.

Sigh...
I did leave in some code. I can't even figure out why it is isn't 
working, let alone why it is causing those strange effects you mentioned.
I will have version 0.3.1 done soon, with a slightly different syntax 
for the glow effect and this code fixed.
Is this a severe problem? I mean, does it actually cause errors, rather 
than just messing up the reporting of errors? If so, I will go ahead and 
post the affected file(tokenize.c).

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message

Chris Huff <chr### [at] maccom> wrote:
: Probably a memory leak

  I think that someone has said that there's a memory leak in at least 99%
of the programs larger than 10000 lines of code.

  That's one of the reasons why you have to be booting windows from time
to time (and in this case the guilty is not necessarily windows itself).

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

Post a reply to this message

In article <39b603a7@news.povray.org>, Warp <war### [at] tagpovrayorg> 
wrote:

>   I think that someone has said that there's a memory leak in at least 99%
> of the programs larger than 10000 lines of code.

Quite true, at least for programs written in the most common languages, 
like C or C++. I suspect there are a couple leaks in the expression 
parsing functions, and maybe two which I added by mistake with the 
turbulence scale patch, but I seem to have been getting leaks since my 
first compile of MegaPOV 0.5a, so it isn't only my code at fault. There 
are probably dozens of small leaks scattered all over the source code.

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message

Chris Huff <chr### [at] maccom> wrote:
: Quite true, at least for programs written in the most common languages, 
: like C or C++.

  In C++ the problem is not so usual because the need for new and delete
has decreased a lot with the introduction of the STL.
  I usually don't use new and delete at all (only when STL really doesn't
do what I want).

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

Post a reply to this message

"Chris Huff" wrote:
> Probably a memory leak,

I don't know exactly what a memory leak is, but I can tell you some more
about how MP+ behaved in my case.

Well, I have this animation that doesn't use any MP+ features at all. When I
render it in regular MP everything is fine and the peak memory used is about
the same for every frame.
But when I render the same animation in MP+ the peak memory used increases
rapidly for every frame, like they are added together. This makes it
practically impossible to render a whole animation.

> if you start over from the frame that caused the trouble, things
> should work fine(until it runs out of memory again).

I don't want to start over 20 times to render a short animation.

> > One strange thing is that in the error messages =, !=, and
> > possible other characters are always replaced with square
> > characters ().
>
> Is this a severe problem? I mean, does it actually cause errors,
> rather than just messing up the reporting of errors?

I don't know if they are directly related. Maybe not.

Rune
--
\ Include files, tutorials, 3D images, raytracing jokes,
/ The POV Desktop Theme, and The POV-Ray Logo Contest can
\ all be found at http://rsj.mobilixnet.dk (updated July 23)
/ Also visit http://www.povrayusers.org

Post a reply to this message

In article <chrishuff-875123.08334206092000@news.povray.org> , Chris Huff 
<chr### [at] maccom>  wrote:

> Quite true, at least for programs written in the most common languages,
> like C or C++. I suspect there are a couple leaks in the expression
> parsing functions, and maybe two which I added by mistake with the
> turbulence scale patch, but I seem to have been getting leaks since my
> first compile of MegaPOV 0.5a, so it isn't only my code at fault. There
> are probably dozens of small leaks scattered all over the source code.

POV-Ray has a memory debugging functionality as a compile-time option.  Look
for it in mem.c.  Enabling it should create a log and further it should be
able to tell you which blocks are not freed after rendering.


       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

In article <39b6503f@news.povray.org>, Warp <war### [at] tagpovrayorg> 
wrote:

>   In C++ the problem is not so usual because the need for new and delete
> has decreased a lot with the introduction of the STL.
>   I usually don't use new and delete at all (only when STL really doesn't
> do what I want).

Hmm, I never use the STL any more...it only caused me trouble.

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message

Chris Huff <chr### [at] maccom> wrote:
: Hmm, I never use the STL any more...it only caused me trouble.

  Strange. I don't use new anymore (except only in very few cases) since
the STL is so handy.

  Why would I code dynamic vectors, trees and so on myself when someone
much more expert than me has done it already? And besides, STL is a lot
easier to use :)

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

Post a reply to this message

In article <39b65b5d$1@news.povray.org>, "Thorsten Froehlich" 
<tho### [at] trfde> wrote:

> POV-Ray has a memory debugging functionality as a compile-time 
> option.  Look for it in mem.c.  Enabling it should create a log and 
> further it should be able to tell you which blocks are not freed 
> after rendering.

Thanks...I remember seeing this before, but it didn't occur to me that 
it could be helpful in doing this.

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message

In article <39b66c38@news.povray.org>, Warp <war### [at] tagpovrayorg> 
wrote:

>   Strange. I don't use new anymore (except only in very few cases) since
> the STL is so handy.
> 
>   Why would I code dynamic vectors, trees and so on myself when someone
> much more expert than me has done it already? And besides, STL is a lot
> easier to use :)

Why would I use code from someone else for something as simple as a 
linked list or tree?
Ok, much of the problem is that I can't find a good reference about the 
best way to use the STL, and templates have been nothing but headaches 
to me.

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message

"Rune" <run### [at] inamecom> writes:

> "Chris Huff" wrote:
> > Probably a memory leak,
> 
> I don't know exactly what a memory leak is, but I can tell you some more
> about how MP+ behaved in my case.
> 
> Well, I have this animation that doesn't use any MP+ features at all. When I
> render it in regular MP everything is fine and the peak memory used is about
> the same for every frame.
> But when I render the same animation in MP+ the peak memory used increases
> rapidly for every frame, like they are added together. 

This is exactly a memory leak: Memory, that has been allocated, is not
freed when it isn't used any more. That's why the program seems to use 
more and more memory during its run.

If you render only a single frame, all memory is freed (returned to the
operating system) when the program ends. By this the memory leak isn't
so apparent.

A "modern" explanation of memory leaks might go like this: Instead of
recycling memory it is thrown away. :-)

Thomas

-- 
http://www.thomas.willhalm.de/ (includes pgp key)

Post a reply to this message

In article <chrishuff-A5A55D.12215206092000@news.povray.org> , Chris Huff 
<chr### [at] maccom>  wrote:

> Why would I use code from someone else for something as simple as a
> linked list or tree?

Because the someone else put a lot of R&D into it and optimised the code for
your platform, while you have to optimise it yourself otherwise...

> Ok, much of the problem is that I can't find a good reference about the
> best way to use the STL, and templates have been nothing but headaches
> to me.

Well, then just use trial and error.  Start with simple types like strings,
vectors and lists first.  Use them in simple cases, play around with them,
and whenever something does not work as expected, try to find out why, don't
just give up.   Don't be afraid, just try - that is how I got started with
it after reading Stroustrup's book :-)

As for books, there are a few in the Addison-Wesley Professional Computing
Series for example (yes, they are expensive, but you can learn a lot from
them, and some will surely be available in your local college library).

Of course there is the Stroustrup "The C++ Programming Language 3rd Ed."
which explains at least the basic types mentioned above well enough to use
them, and it also explains templates.  For understanding the complex object
oriented models behind lots of libraries (not just the STL, but also i.e.
most GUI frameworks) try the classic book "Design Patterns: Elements of
Reusable Object-Oriented Software".


     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

Chris Huff wrote in message ...
>I suspect there are a couple leaks in the expression
>parsing functions, and maybe two which I added by mistake with the
>turbulence scale patch, but I seem to have been getting leaks since my
>first compile of MegaPOV 0.5a, so it isn't only my code at fault. There
>are probably dozens of small leaks scattered all over the source code.


Last year I went through POV-Ray for Windows (the SuperPatch version) and
got rid of every memory leak the memory-logging function could find.  Most
of the leaks were in SuperPatch features.  The ones I have the fixes for
are:

Spline memory leak
-- Add the following lines to the end of Destroy_Ident_Data
     case SPLINE_ID_TOKEN:
       Destroy_Spline((SPLINE *)Data);
       break;

Memory leak in File:C:\Temp\workarea\SOURCE\Matrices.c  Line: 986  Size:256
 --Problem occurs when a declared object (HF?) is scaled and then instanced
 -- THE BUG:  COPY_OBJECT_FIELDS copies the UV_Trans for an object, but
Copy_Object also does this.  The fix: remove the call in Copy_Object.

One warning about the memory log feature:  It results in about a 30%
slowdown in rendering SkyVase.  Be sure to turn it off when compiling a
release version.

Mark

Post a reply to this message

Chris Huff wrote:
> 
> Ok, much of the problem is that I can't find a good reference about the
> best way to use the STL, and templates have been nothing but headaches
> to me.
> 

	Two links for the STL:
http://codeguru.earthweb.com/cpp/stlguide/index.shtml
http://www.sgi.com/Technology/STL/

	And a genral book about C++ with (among other things) a good
introduction to templates:
http://codeguru.earthweb.com/cpp/tic/index.shtml

		Jérôme
-- 
******************************* Jérôme M. BERGER
* Doctor Jekyll had something * mailto:ber### [at] inamecom
* to Hyde...                  * http://www.enst.fr/~jberger
*******************************

Post a reply to this message

In article <39b72862@news.povray.org>, "Mark Wagner" 
<mar### [at] gtenet> wrote:

> Last year I went through POV-Ray for Windows (the SuperPatch version) and
> got rid of every memory leak the memory-logging function could find.  
> Most of the leaks were in SuperPatch features.  The ones I have the 
> fixes for are:

I added these fixes to my version, thanks!

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message

In article <39b6892f@news.povray.org>, "Thorsten Froehlich" 
<tho### [at] trfde> wrote:

> Because the someone else put a lot of R&D into it and optimised the 
> code for your platform, while you have to optimise it yourself 
> otherwise...

Aw, takes all the fun out of it! ;-)


> Well, then just use trial and error.  Start with simple types like 
> strings, vectors and lists first.  Use them in simple cases, play 
> around with them, and whenever something does not work as expected, 
> try to find out why, don't just give up.   Don't be afraid, just try 
> - that is how I got started with it after reading Stroustrup's book 
> :-)

Ok...I will try. :-)
But you have seen CodeWarrior's error messages...not terribly 
descriptive. I spent most of my time in the "error" portion of "trial 
and error".

...misc book recommendations snipped...
Thanks, I will put these on my list of books to get.

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message

In article <chrishuff-240B6F.16040107092000@news.povray.org> , Chris Huff 
<chr### [at] maccom>  wrote:

> Ok...I will try. :-)
> But you have seen CodeWarrior's error messages...not terribly
> descriptive. I spent most of my time in the "error" portion of "trial
> and error".
>
> ...misc book recommendations snipped...
> Thanks, I will put these on my list of books to get.

Guess what, other compilers are even worse <sigh>   MrC and Visual C for
example...


      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

In article <chrishuff-240B6F.16040107092000@news.povray.org> , Chris Huff 
<chr### [at] maccom>  wrote:

> ...misc book recommendations snipped...
> Thanks, I will put these on my list of books to get.

See it this way:  If you plan to major in CS (if you do?) you will have to
get most of them sooner or later anyway ;-)


    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

In article <chrishuff-0559FE.12183706092000@news.povray.org>, Chris 
Huff <chr### [at] maccom> wrote:

> Thanks...I remember seeing this before, but it didn't occur to me that 
> it could be helpful in doing this.

Well, by using this logging feature, I was able to find a couple leaks 
and confirm some I had found before. Some of the leaks I haven't figured 
out how to fix yet are in the UseMediaAndLightCache patch, these 
variables are allocated but never released:
ShadowMediaListCacheSize
LightingMediaListCacheSize
MediaIntervalCacheSize

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message

In article <39b80909$1@news.povray.org>, "Thorsten Froehlich" 
<tho### [at] trfde> wrote:

> > Thanks, I will put these on my list of books to get.
> 
> See it this way:  If you plan to major in CS (if you do?)

I do(though I have not decided the exact areas)...


> you will have to get most of them sooner or later anyway ;-)

 ...and I know I will. :-)
Especially graphics and algorithms books, all I have are "introduction 
to C/C++/Java" books and one good C++ intro/reference book(C++ Primer 
Plus, which does cover the STL, just in a somewhat incomprehensible way 
for someone who doesn't already use it).
Hmm, maybe I can get my parents to pay for them...probably not.

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message

Thanks, I will take a look at these sites.

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message

Chris Huff <chr### [at] maccom> wrote:
: Why would I use code from someone else for something as simple as a 
: linked list or tree?

  A list is rather simple, but it's not unusual at all that you make mistakes
easily (memory leaks, reading freed memory...).
  A weighted binary tree IS NOT easy at all to do. You have to code quite a
lot to get one done. Why should I do it when it's already done. And done well.

  I always like to show in these cases this example I made:

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{ typedef map<string,unsigned> wlist_t;
  wlist_t words;
  string word;
  while(cin) { cin >> word; words[word]++; }
  for(wlist_t::iterator i=words.begin(); i!=words.end(); i++)
    cout << i->first << ": " << i->second << endl;
}


  It reads words from the standard input (a word is limited by whitespaces)
and then outputs an alphabetically ordered list of the words and a number
indicating the amount of times the word appears in the text.

  Try to make that without using any STL. It must be at least as fast as
this one.
  How many code lines do you need? How much time do you need to make it?

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

Post a reply to this message

In article <39b8cf06$1@news.povray.org>, Warp <war### [at] tagpovrayorg> 
wrote:

>   A list is rather simple, but it's not unusual at all that you make 
> mistakes easily (memory leaks, reading freed memory...).

My first version of the new glow patch being an embarassing example of 
this...


>   A weighted binary tree IS NOT easy at all to do. You have to code quite 
> a lot to get one done. Why should I do it when it's already done. And 
> done well.

Because I want to know how to do it? And because I don't want to be 
separated from what my program is doing? And because when I was *trying* 
to learn the STL, I often got errors and couldn't figure out why?

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message

Chris Huff <chr### [at] maccom> wrote:
:>   A weighted binary tree IS NOT easy at all to do. You have to code quite 
:> a lot to get one done. Why should I do it when it's already done. And 
:> done well.

: Because I want to know how to do it?

  So instead of spending 1/2 hour once to learn how to use the STL you
spend 2 hours every time you want to use a weighted binary tree?

: And because I don't want to be 
: separated from what my program is doing?

  Sorry, I didn't understand at all what are you talking about here.

: And because when I was *trying* 
: to learn the STL, I often got errors and couldn't figure out why?

  Get a proper compiler and try again. You can get one by free.

  And read documentation and tutorials.

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

Post a reply to this message

In article <chrishuff-078CCD.07512408092000@news.povray.org> , Chris Huff 
<chr### [at] maccom>  wrote:

>>   A weighted binary tree IS NOT easy at all to do. You have to code quite
>> a lot to get one done. Why should I do it when it's already done. And
>> done well.
>
> Because I want to know how to do it? And because I don't want to be
> separated from what my program is doing?

Hmm, sounds like reinventing the wheel to me ;-)

The thing is once you have done it two or three times it gets really boring
writing the same code over and over again and it distracts from the fun part
of programming and especially it distracts from the actual problem you want
to solve.

I think all data structures the STL provides are listed in yet another set
of classic books "Introduction to Algorithms" for the more practical
information should cover them, and the books by Knuth, especially "The Art
of Computer Programming" without question include all of algorithms used in
the STL in a very detailed and abstract manner (NOTE: Neither of these books
has anything to do with the actual STL, they are pure computer science
books).  Actually, most STLs likely use suggested implementations you find
in one of his books :-)


       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

In article <39b9050f@news.povray.org> , Warp <war### [at] tagpovrayorg>  wrote:

> : And because when I was *trying*
> : to learn the STL, I often got errors and couldn't figure out why?
>
>   Get a proper compiler and try again. You can get one by free.

Actually, CodeWarrior is a good (not perfect) compiler with a really good
and ISO C++ standard compliant _library_.  The only not supported ISO C++
language feature (and thus it is not fully compliant to the ISO C++
standard...) is the "export" keyword for templates (section 14, paragraph
6), but I know only very few compilers that support it (if you know one for
IRIX or Mac OS, I am interested!).

The library itself passes all special cases listed in the ISO C++ standard
as well as the ones in The C++ Prog. Lang. 3rd Ed, Appendix B (I tried those
myself).  CodeWarrior is also supposed to (I never checked) support the
minimum limits listed in Annex B of the ISO C++ standard.

As for the STL, being compliant causes a lot of problems with other
compilers.  Take a look at gcc and the iostreams it comes with.  They are so
far behind the standard, you need to make fixes all over the place to get it
to work cross-platform.

>   And read documentation and tutorials.

Now, when you buy a book that covers STL, you have one of two problems:
Either it doesn't cover the ISO C++ STL or it does and you can't use it with
a lot of compilers (Visual C 5.0 also had a lot of problems, 6.0 seems to be
better, gcc is still a mess).

This example does apply when trying to compile CodeWarrior code with Visual
C++ 5.0 (it happened to me!!!):
If you get an error message you end up having to analyse error messages and
try to figure out what is wrong.  Sometimes these error messages can be
impossible to understand when you assume you have a compliant library.  My
mistake was to use a "getchar" member function in one class.  Too bad, some
compiler libraries have not been updated to the ISO C++ standard (which
requires this to be a function!) and it is still a macro.  Now, your
compiler will always tell you something about an illegal class declaration,
but everything looks OK!!!

Now, this isn't even an example with an STL problem and it can still be hard
to understand the problem.  Try making a simple mistake just like declaring
a nested template with '>>' at the end.  How useful is the error message you
get from _your_ compiler?


     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

In article <39b8cf06$1@news.povray.org> , Warp <war### [at] tagpovrayorg>  wrote:

>   I always like to show in these cases this example I made:
>
> #include <iostream>
> #include <map>
> #include <string>
> using namespace std;
> int main()
> { typedef map<string,unsigned> wlist_t;
>   wlist_t words;
>   string word;
>   while(cin) { cin >> word; words[word]++; }
>   for(wlist_t::iterator i=words.begin(); i!=words.end(); i++)
>     cout << i->first << ": " << i->second << endl;
> }

Is this by any chance the only example you have? ;-)


      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

In article <39b8cf06$1@news.povray.org> , Warp <war### [at] tagpovrayorg>  wrote:

> #include <iostream>
> #include <map>
> #include <string>
> using namespace std;
> int main()
> { typedef map<string,unsigned> wlist_t;
>   wlist_t words;
>   string word;
>   while(cin) { cin >> word; words[word]++; }
>   for(wlist_t::iterator i=words.begin(); i!=words.end(); i++)
>     cout << i->first << ": " << i->second << endl;
> }

The return is missing...

>
>   It reads words from the standard input (a word is limited by whitespaces)
> and then outputs an alphabetically ordered list of the words and a number
> indicating the amount of times the word appears in the text.
>
>   Try to make that without using any STL. It must be at least as fast as
> this one.
>   How many code lines do you need? How much time do you need to make it?

Hmm, lets see, you need (runtimes from the C++ Prog. Lang 3rd Ed. page
464)...

For inserting:       O(n * log(n))
For retrieval:       O(n * log(n))
Total:               O(n * log(n) + n * log(n))


I can get:

For inserting:       O(n)
For sorting *:       O(n * log(n))
For retrieval:       O(n)
Total:               O(2 * n + n * log(n))

* No fancy algorithm, just quicksort.


How?  That is simple:  I read in the words. Then sort them and then just
count when retrieving.

Of course I can do this using the STL (see below)!  But your example shows
something dangerous you forgot:  the STL can trick you into thinking you
have found a good algorithm, but in fact yours is nearly log(n) times slower
than mine for most cases (for log(n) > 2)!

The condensed version (readable version at the end):

#include <iostream>
#include <list>
#include <string>
using namespace std;
void main() {
    typedef list<string> wlist_t;
    wlist_t words;
    string word;
    while(cin) { cin >> word; words.push_back(word); }
    words.sort();
    for(wlist_t::iterator i = words.begin(); i != words.end();) {
        wlist_t::iterator temp = i; int cnt = 0;
        for(; i != words.end(); i++, cnt++) if(*i != *temp) break;
        cout << *temp << ": " << cnt << endl;
}   }


Note that I can also provide a standard C only version which is less than
twice the length, supports dynamic string length and should be slightly
faster that this version by using some tricks.


      Thorsten


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

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




The more readable version of my program:


#include <iostream>
#include <list>
#include <string>

using namespace std;

void main()
{
    typedef list<string> wlist_t;
    wlist_t words;
    string word;

    while(cin)
    {
        cin >> word;
        words.push_back(word);
    }

    words.sort();

    for(wlist_t::iterator i = words.begin(); i != words.end();)
    {
        wlist_t::iterator temp = i;
        int cnt = 0;

        for(; i != words.end(); i++, cnt++)
        {
         if(*i != *temp)
          break;
        }
        cout << *temp << ": " << cnt << endl;
    }
}

Post a reply to this message

Yo, Chris,  when can we expect the fixed version of the +.3?  The memory
leak has sorta crippled my IRTC anim...  
Oops.
:)

H.E. Day

Post a reply to this message

On Fri, 08 Sep 2000 13:36:17 -0500, Thorsten Froehlich wrote:
>For inserting:       O(n * log(n))
>For retrieval:       O(n * log(n))
>Total:               O(n * log(n) + n * log(n))
>
>
>I can get:
>
>For inserting:       O(n)
>For sorting *:       O(n * log(n))
>For retrieval:       O(n)
>Total:               O(2 * n + n * log(n))
>
>* No fancy algorithm, just quicksort.

You seem to have a misconception about how O() notation works.  The total
for the first case is O(n*log(n)) and the total for the second case is...
O(n*log(n)).  They might have different constant factors, but the determination
of which is faster is entirely a matter of determining those constant factors
(which depend on the constant factors in the component parts of the algorithm.)

BTW, if this comparison method worked, I could beat you both.  I have a 
balanced, fully-threaded 2-3 tree implementation with O(n log n) insertion
and O(n) traversal.

-- 
Ron Parker   http://www2.fwi.com/~parkerr/traces.html
My opinions.  Mine.  Not anyone else's.

Post a reply to this message

In article <39b9050f@news.povray.org>, Warp <war### [at] tagpovrayorg> 
wrote:

>   So instead of spending 1/2 hour once to learn how to use the STL you
> spend 2 hours every time you want to use a weighted binary tree?

No, I want to spend 2-5 hours learning how to implement it myself. Then 
I can spend 1.5 hours figuring out the STL(or fighting with the STL) to 
do the same thing.


> : And because I don't want to be 
> : separated from what my program is doing?
> 
>   Sorry, I didn't understand at all what are you talking about here.

If I use the STL, I don't know exactly what is happening in my program. 
If something goes wrong with a program using something I implemented, I 
know the code, and can figure out the problem quickly. If something goes 
wrong and I am using the STL, I end up trying to figure out why STL 
files are producing errors, whether or not the problem is actually *in* 
the STL.


> : And because when I was *trying* 
> : to learn the STL, I often got errors and couldn't figure out why?
> 
>   Get a proper compiler and try again. You can get one by free.

I have an excellent compiler and good libraries. That doesn't help 
understanding the reasons I get errors.


>   And read documentation and tutorials.

I have been collecting links to various STL tutorials/overviews on the 
web. I also plan to buy some books, when I can. I have a book with a lot 
of detailed information on the STL, but it seems more reference oriented 
than tutorial oriented.

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message

In article <39b91926@news.povray.org>, "Thorsten Froehlich" 
<tho### [at] trfde> wrote:

> Hmm, sounds like reinventing the wheel to me ;-)

Exactly.


> The thing is once you have done it two or three times it gets really 
> boring writing the same code over and over again and it distracts 
> from the fun part of programming and especially it distracts from the 
> actual problem you want to solve.

That is fine, but at the moment, I want to have a grasp of how they 
work. I can imagine programmers taught to always use the STL 
encountering a simple doubly linked list in someone else's code and 
being completely baffled by it...I want to understand the tools I use, 
and how to implement them myself if necessary. For example: a game 
project with extremely severe speed requirements, developing for 
platforms where the STL isn't useable, writing in other languages which 
I may learn in the future, etc. Especially that last one...I don't 
expect C++ and STL to last forever, knowledge of algorithms is portable, 
knowledge of the STL is not.

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message

In article <01c019ce$7da07900$917889d0@daysix>, "H. E. Day" 
<Pov### [at] aolcom> wrote:

> Yo, Chris,  when can we expect the fixed version of the +.3?  The memory
> leak has sorta crippled my IRTC anim...  

Real Soon Now. I have a couple more things to work out, and a couple 
small features I want to add.

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message

In article <slr### [at] fwicom> , ron### [at] povrayorg (Ron
Parker) wrote:

> You seem to have a misconception about how O() notation works.  The total for
> the first case is O(n*log(n)) and the total for the second case is...

I know, but I don't care enough (especially as a full "prove" is rather
long) as all I want to point out is that a map will not perform better than
a slightly different and in plain C easier to write algorithm than the
RB-tree most likely used for the map.   As for the total, you are right that
I shouldn't just have copy and pasted it together assuming anybody would get
the idea I wanted to show.

> O(n*log(n)).  They might have different constant factors, but the
> determination of which is faster is entirely a matter of determining those
> constant factors (which depend on the constant factors in the component parts
> of the algorithm.)

Yes, I am aware the constants matter here when using a simple sorting method
(merge sort) as I suggested.

To make you happy, I could have written (for the worst cases):

Numbers following variables should be read as subscripts!


T1(n) = (c1 * n * log n + c2) + (c3 * n * log n + c4) =
        (c1 + c3) * n * log n + (c2 + c4)

T2(n) = (c5 * n + c6) + (c7 * n + c8) + (c9 * n * log n + c10) =
        (c5 + c7) * n + (c9 * n * log n) + (c6 + c8 + c10)

For a large enough n this will hold:

c2 + c4 < (c5 + c7) * log n

and

c6 + c8 + c10 < (c5 + c7) * log n


So, I simply eliminate c2, c4, c6, c8 and c10 (set them to one) and can get:

T1(n) = (c1 + c3) * n * log n

T2(n) = (c5 + c7) * n + (c9 * n * log n)

Lets further assume that c1 = c3:

T1(n) = 2 * c1 * n * log n

T2(n) = (c5 + c7) * n + (c9 * n * log n)


And now comes the tricky part because I have to show that (c1 + c3) > c9.  I
do not need to assume anything about c5 and c7 as n * log n > n for a big
enough n. this leaves:

T1(n) = 2 * c1 * n * log n

T2(n) = c9 * n * log n

I assume that for map a RB-tree is used and for list.sort a merge sort that
just flips the pointers of two strings.  In both cases the algorithms need
to perform n * log n string comparisons, so we can just not count those.

This leaves the recursive calls and the swap operation for the merge sort,
and the walking through the tree (twice).

I assume that the merge sort will be faster*, but if anybody is not happy
with this, for string sorting there are plenty of other algorithms out
there...

In conclusion it is without problems possible to outperform the map used in
this case, and this is all I wanted to point out.


     Thorsten


* I don't want to spend the time to show this now.


____________________________________________________
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

In article <slr### [at] fwicom> , ron### [at] povrayorg (Ron
Parker) wrote:

>>For inserting:       O(n * log(n))
>>For retrieval:       O(n * log(n))
>>Total:               O(n * log(n) + n * log(n))
>>
>>
>>I can get:
>>
>>For inserting:       O(n)
>>For sorting *:       O(n * log(n))
>>For retrieval:       O(n)
>>Total:               O(2 * n + n * log(n))
>>
>>* No fancy algorithm, just quicksort.
>
> You seem to have a misconception about how O() notation works.  The total for
> the first case is O(n*log(n)) and the total for the second case is...
> O(n*log(n)).  They might have different constant factors, but the
> determination of which is faster is entirely a matter of determining those
> constant factors (which depend on the constant factors in the component parts
> of the algorithm.)
>
> BTW, if this comparison method worked, I could beat you both.  I have a
> balanced, fully-threaded 2-3 tree implementation with O(n log n) insertion
> and O(n) traversal.

(Referring to my previous reply):
Or, I could just prove that

 lim   2n lg n   >   lim   2n + n lg n
n->oo               n->oo

=>

 lim   n lg n  >   lim   2n
n->oo             n->oo


        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

On Fri, 08 Sep 2000 13:36:17 -0500, Thorsten Froehlich wrote:
>Total:               O(n * log(n) + n * log(n))

which is O(n * log(n)

>Total:               O(2 * n + n * log(n))

which is also O(n * log(n)

No difference there.

Which one of the two algorithms is really faster depends on the
implementation and the input data.

	hp

-- 
   _  | Peter J. Holzer    | Nicht an Tueren mangelt es,
|_|_) | Sysadmin WSR       | sondern an der Einrichtung (aka Content).
| |   | hjp### [at] wsracat      |    -- Ale### [at] univieacat
__/   | http://www.hjp.at/ |       zum Thema Portale in at.linux

Post a reply to this message

In article <slr### [at] tealhhjpat> , 
hjp### [at] SiKituwsracat (Peter J. Holzer) wrote:

>>Total:               O(n * log(n) + n * log(n))
>
> which is O(n * log(n)
>
>>Total:               O(2 * n + n * log(n))
>
> which is also O(n * log(n)
>
> No difference there.

Yes, because I was lazy and just did a copy and paste.  In big-O notation
this will be the result, but this is not the whole issue (just eliminate the
big-O in the total!).

> Which one of the two algorithms is really faster depends on the
> implementation and the input data.

No, it is a clear which one is faster, just my notation for the total was
incorrect:  See my later posts explaining it in more detail.


      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

In article <slr### [at] tealhhjpat> , 
hjp### [at] SiKituwsracat (Peter J. Holzer) wrote:

> Which one of the two algorithms is really faster depends on the
> implementation and the input data.

No, it does not depend on the input data too much.  The reason being that
the tree used for the map will be balanced so you should always have about
log n access time.  And for the merge sort it also does not matter, it will
always take n log n time.

I fell for the trap of the big-O notation at first, too, when replying to
Ron, but I was simply implying the wrong thing at first by using big-O
notation for the totals, especially because you can't compare big-Os of
functions anyway ...


      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

Chris Huff wrote:

> > you will have to get most of them sooner or later anyway ;-)
>
>  ...and I know I will. :-)
> Especially graphics and algorithms books, all I have are "introduction
> to C/C++/Java" books and one good C++ intro/reference book(C++ Primer
> Plus, which does cover the STL, just in a somewhat incomprehensible way
> for someone who doesn't already use it).
> Hmm, maybe I can get my parents to pay for them...probably not.

Have you got

"Code Complete" - Steve McConnell

"The Mythical Man-Month" - Frederick P. Brooks Jr.  (anniversry edition)

"Peopleware" - Demarco & Lister

"Rapid Development" - Steve McConnell

"Extreme Programming Explained" - Kent Beck


Of those, I'd say the first two are a must for you for now, and the others
are for as you get time.

Post a reply to this message

>Real Soon Now... and a couple
> small features I want to add.

famous last words of all programmers.

Post a reply to this message

> and how to implement them myself if necessary. For example: a game
> project with extremely severe speed requirements, developing for
> platforms where the STL isn't useable,

read "Game Architecture and Design" by Rollings and Morris and you'll
realize these notions are very outdated.  programs are getting too big,
and computers too fast for any one person or team to develop all the
code in-house or worry about speed optimization.  libraries are the
future.  just look at the quake engines.  those are libraries.  other
developers are starting to make other specific libraries, like physics,
installation, or interface libraries.  the book i mentioned talks about
this and has application for all fields of software development; it just
goes in to games a little more.

Post a reply to this message

In article <39B9D82F.9D3E3C56@yahoo.com>, ryan constantine 
<rco### [at] yahoocom> wrote:

> read "Game Architecture and Design" by Rollings and Morris and you'll
> realize these notions are very outdated.  programs are getting too big,
> and computers too fast for any one person or team to develop all the
> code in-house or worry about speed optimization. 

This is true for most applications, but only gets rid of one of my 
arguments, and isn't applicable to all situations.
What about my other arguments? Platforms where the STL doesn't exist or 
is too bulky, new languages, etc.


> libraries are the future.  just look at the quake engines.  those are 
> libraries.  other developers are starting to make other specific 
> libraries, like physics, installation, or interface libraries. 

This has very little to do with the reason I want to learn those 
algorithms. Besides, I might end up programming one of those libraries! 
They don't just come out of nowhere, they are written by programmers who 
know how to do that stuff.

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message

In article <39B9D612.294DF35E@yahoo.com>, ryan constantine 
<rco### [at] yahoocom> wrote:

> >Real Soon Now... and a couple
> > small features I want to add.
> 
> famous last words of all programmers.

Specifically, there are two features I want to add:
A small optimization in case of "turbulence 0", maybe for all places 
that can use turbulence.
Glow transformations.

I have added two new glow types, but they are unfinished(they don't work 
right when the glow is covered by or partly embedded in an object). I 
don't plan to finish them before releasing a new version, though.

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message

| I have added two new glow types, but they are unfinished(they don't work 
| right when the glow is covered by or partly embedded in an object). I 
| don't plan to finish them before releasing a new version, though.

What two new glow types?  Enlighten me!

H.E. Day
<><

Post a reply to this message

In article <01c01a81$c5b12c40$697889d0@daysix>, "H. E. Day" 
<Pov### [at] aolcom> wrote:

> What two new glow types?  Enlighten me!

A sphere glow with constant density(sort of like a transparent sphere 
with fade_color, but a bit faster and doesn't require intersection 
calculations), and a glow using the exp() function.

I added a keyword to scale the size, and added another keyword to limit 
the glow to a spherical area(this might speed some scenes up). The 
keywords are "size" and "radius".

I added a falloff exponent feature, to adjust the rate at which the glow 
dims with distance.

I have removed the turbulence feature, but you can now specify any 
warps. It will be slightly slower with turbulence and the same speed 
without it, but you will have more flexibility now, with black holes, 
displace warps, etc.

I added the ability to transform the glow. Scaling only affects the 
position, though, since there are currently only point sources.

And here are some features which won't be in the next version, but which 
I am planning:
A pigment to control the color(definitely not realistic, but potentially 
useful).

Different rendering modes: emission/additive, like it does now, 
multiplicative, a mode which imitates scattering media, with constant 
density(or some density functions which can be calculated directly), etc.

And I still haven't added that optimization for "turbulence 0", it isn't 
a very high priority, since there is an obvious workaround.

I am also thinking of a similar lens flare feature. A separate patch, 
not part of the glow feature, but based on the same rendering methods, 
and with additional stuff to make it more flare-like.

-- 
Christopher James Huff
Personal: chr### [at] maccom, http://homepage.mac.com/chrishuff/
TAG: chr### [at] tagpovrayorg, http://tag.povray.org/

<><

Post a reply to this message

Thorsten Froehlich <tho### [at] trfde> wrote:
: If you get an error message you end up having to analyse error messages and
: try to figure out what is wrong.

  This is a very common problem with templates (specially ones that have
many parameters).
  I don't think there's any bullet-proof solution to the problem. When I really
want to analyze an error message which mentions some STL template, I filter
it (with sed or perl) to get rid of the template parameters. The error message
gets a lot clearer.
  Usually I don't need to decipher the error message. I only look at the
line of code (ie. in my code) that caused the problem and usually see what
it was. Some times it's more difficult, however. Some error types you just have
to know to see them (eg. trying to use a class without copy constructor with
STL).

: Now, this isn't even an example with an STL problem and it can still be hard
: to understand the problem.  Try making a simple mistake just like declaring
: a nested template with '>>' at the end.  How useful is the error message you
: get from _your_ compiler?

  Believe me, the error messages of gcc are MYSTICAL! :)

  For example, can you say what causes this error message?

request for member `clear' in `x', which is of non-aggregate type `string ()()'


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

Post a reply to this message

Chris Huff <chr### [at] maccom> wrote:
: If I use the STL, I don't know exactly what is happening in my program. 
: If something goes wrong with a program using something I implemented, I 
: know the code, and can figure out the problem quickly. If something goes 
: wrong and I am using the STL, I end up trying to figure out why STL 
: files are producing errors, whether or not the problem is actually *in* 
: the STL.

  Do you use the string class? Do you use streams? Do you use any standard
function?
  Do you know exactly what does each one of them do?

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

Post a reply to this message

Thorsten Froehlich <tho### [at] trfde> wrote:
: Is this by any chance the only example you have? ;-)

  Yes. And why not? I could write more similar examples, but what would
be the point? I think one is enough.

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

Post a reply to this message