The Doryen Library 1.3.2 + The Doryen Arena 0.7 released
jice
fast generic container TCODList.
http://jice.nospam.googlepages.com/thedoryenlibrary
arena 0.7 has slightly improved and easier gameplay :
* more player feedback (you can see if a creature is stunned without
looking at its conditions)
* increased difference between weapon classes through special effects
(swords make bleed, hammer stun, masses stun and weaken, axes stun,
weaken and make bleed)
* a new adrenaline bar allowing you to use a powerful weapon-specific
special attack
* a new "custom fight" game mode making it possible to fight any
opponent panel
* new weather lightning effect
http://jice.nospam.googlepages.com/arena
--
jice
stu
> libtcod 1.3.2 is a bugfix release. It also adds documentation for the
> fast generic container TCODList.
>
neat you re-invented a basic data structure.. The Array!
Why call it a list when its really an array and not a list at all?
Are you going to implement for us
TCODSingleLinkList
TCODDoubleLinkList
TCODBucketList
TCODQueue
TCODStack
TCODRingBuffer
TCODSuperFastSort
TCODBTree
TCODRedBlackTree
?
I think you should cap the new list size to say 64 entries growth
each time rather than count * 2, it will reduce a lot of empty
entries when the array starts to grow.
also, you should have a call back for destroying the list
to help with memory management.
Implementing as an array makes insertion/removal of anything
but the tail a long process, which as implemented by a for loop
is much longer than a straight up memmove.
The only time a List implemented as an Array as you have pays
off is if you know the arbitrary index of an item you want to
access.
-Stu
Nathan D. Jerpe
news:e953e000-24a0-4b83...@y21g2000hsf.googlegroups.com...
On Jul 14, 5:31 am, jice <jice.nos...@gmail.com> wrote:
> libtcod 1.3.2 is a bugfix release. It also adds documentation for the
> fast generic container TCODList.
>
>neat you re-invented a basic data structure.. The Array!
>Why call it a list when its really an array and not a list at all?
C'mon now nobody's paying jice to do this.
You've got some valid criticisms, and I'm willing to bet that jice will
consider them. But a little encouragement goes a long way too.
Nathan
http://roguelikefiction.com
zai...@zaimoni.com
> libtcod 1.3.2 is a bugfix release. It also adds documentation for the
> fast generic container TCODList.
>
> http://jice.nospam.googlepages.com/thedoryenlibrary
It would be nice to have a more confidence-inspiring URL for the
download link (one that doesn't claim 1.3.1, etc.)
zai...@zaimoni.com
> On Jul 14, 5:31 am, jice <jice.nos...@gmail.com> wrote:
>
> > libtcod 1.3.2 is a bugfix release. It also adds documentation for the
> > fast generic container TCODList.
>
> neat you re-invented a basic data structure.. The Array!
> Why call it a list when its really an array and not a list at all?
While I empathize (cf my flamewar on the converse notation error in
Python: calling an array a list), I would not have mentioned that
here.
> ....
>
> Implementing as an array makes insertion/removal of anything
> but the tail a long process, which as implemented by a for loop
> is much longer than a straight up memmove.
IMO, the C version should be rewritten to use memmove and realloc.
(However, I don't actually use libtcod, I just archive it locally for
reference.)
The C++ version is trickier (but then again, std::vector is a moderate-
weight TCODList). algorithm is one of the moderate-weight headers on
GCC, so std::copy isn't a real option for a lightweight class. (A
competent implementation of std::copy will reduce to memmove when
appropriate).
> The only time a List implemented as an Array as you have pays
> off is if you know the arbitrary index of an item you want to
> access.
I wish. An array is also useful for avoiding dynamic memory manager
overhead, by minimizing the total number of pointers allocated.
However, I'm not sure this is actually a concern for libtcod.
(Yes, a properly implemented non-robust general C/C++ memory manager
can be sublinear in the number of already existing pointers for both
allocation and deallocation.)
jice
> neat you re-invented a basic data structure.. The Array!
> Why call it a list when its really an array and not a list at all?
Hey put down the big guns ! The list is already used internally by the
library, so I just thought it would be cool for it to be documented,
so that developers that are looking for a simple container don't
bother creating it from scratch in C or use STL in C++. Of course it
could be a little faster, but everybody knows a container can't be
faster for all operations. Either you have fast push operations, or
fast insertions, or fast index access... This implementation is "fast
enough" for most common operations and very simple to use. That's the
whole philosophy behing libtcod. Nobody is forced to use it.
On 14 juil, 17:12, zaim...@zaimoni.com wrote:
> It would be nice to have a more confidence-inspiring URL for the
> download link (one that doesn't claim 1.3.1, etc.)
Err right, they were pointing to the old 1.3.1 packages. It's fixed
now. Thanks.
--
jice
jot...@hotmail.com
meant to be a good RL starter kit (covering all aspects of building a
RL, not just for experienced programmers, but also for beginners),
many could start with a giant mess of arrays and/or pointers (home-
made linked lists) as I did a while back, and while that's good as a
learning experience, it can break an otherwise decent RL. Not to
mention the morale buster of dealing with such "complex" issues, in
the mind of a wannabe programmer.
I'd like to be able to introduce people to coding a RL and not go "oh,
then there's this thing with lists... arghh.. use an array.. here's
now to insert and delete elements.. index minus one... etc". It's much
better to just say "here's a simple list you can use, call these
functions, then when you're comfortable with programming you can take
up other stuff".
Yes I tutor a lot.
:)
Jotaf
jice
True. I believe a pretty important part of the developers using
libtcod are C/C++ beginners. Having a container out of the box will
probably save them a lot of pain. But that doesn't mean it's low
quality stuff. This is the only container I use in Arena and TCOD and
I don't think they are beginner programs...
--
jice
stu
> True. I believe a pretty important part of the developers using
> libtcod are C/C++ beginners. Having a container out of the box will
> probably save them a lot of pain. But that doesn't mean it's low
> quality stuff. This is the only container I use in Arena and TCOD and
> I don't think they are beginner programs...
Well, I didnt say the rest of the lib was bad, I think its quite cool.
I'd be using it if it came out before I started writing cnc and rolled
my own sdl interface. I'd rather see people use it over curses, its
time
we all moved from curses to SDL! :)
I think the list code is low quality compared to the rest of TCOD,
your using for loops to move large chunks of contiguous memory
around, thats plain lazy when you can just memmove and be done.
if it works, it works right, its just one of those things I happened
to look at and go aaargh during my teabreak at work :), and I'd rather
look at TCOD than SAP....
-stu
jot...@hotmail.com
> True. I believe a pretty important part of the developers using
> libtcod are C/C++ beginners. Having a container out of the box will
> probably save them a lot of pain. But that doesn't mean it's low
> quality stuff. This is the only container I use in Arena and TCOD and
> I don't think they are beginner programs...
>
> --
> jice
I didn't say anything about its quality, it seems pretty good; my main
point is that it's beginner-friendly. A programmer will eventually
learn linked lists and array operations, etc. Not to "code something
better", but (most importantly) because they need to know how these
things work, and (least importantly) to be able to design a library
that fits a demanding system better than a generic list. But IMO this
knowledge isn't needed when starting out; that's like starting to
build a house from the top.
Jotaf
jice
(warning, troll inside...) Honestly, I can't understand how one can
use a library as user-unfriendly as curses... Some like their code
being plagued with mvaddchnstr and mvwadd_wchnstr... This sounds like
mordor's black speech for me... :P
> I think the list code is low quality compared to the rest of TCOD,
> your using for loops to move large chunks of contiguous memory
> around, thats plain lazy when you can just memmove and be done.
I don't think it matters :
* memmove is nothing else than a for loop moving large chunks of
contiguous memory. Ok, it will be faster than an optimized C loop, but
not that faster, so the gain will be noticeable only if you intend do
do billions of insertions.
* TCODList has blazing fast push/pop operations, iterators and index
access. It will never have fast insertions. So if I had to do billions
of insertions, I would certainly not use it because it will be slow,
even with memmove. If you definitely need those billions of
insertions, then you'll have to write your own container, specifically
designed for this use because a general all-purposes container can't
be used in every performance-intensive scenario.
Now I'll replace the loop with a memmove call just to keep you from
aaarghing, but there won't be any noticeable change in the programs
using TCODList :P
Concerning the list reallocation, I think adding a constant amount of
entries, like 64 is bad. Try to allocate a list with 10 000 elements
and you need 156 reallocations... This is slow and will have
noticeable impact on the game performances. And you will lose lots of
memory too if you have a lot of small lists with only a few elements.
On the other hand, by doubling the size each time, you can allocate in
the worst case twice the amount of memory actually needed. This is
bad, but it can be an issue only if you allocate a 256Mb container.
I'll add a constructor allowing you to preallocate the right size.
Finally, for the memory callback, you can free the memory by
destroying the TCODList object. If you mean freeing memory when you
remove elements from the list, I think it's bad too. If your list
contains 1000 elements at some point, then only 50, there's a good
chance it will grow up to 1000 again, so freeing memory to reallocate
it later will only make your program slower. If you need 1000 elements
in the initialization phase, then only 50 during the game, you
shouldn't use the same list. Destroy the 1000 elements list and create
a new one for the 50 remaining.
Arena and TCOD use no other general container than TCODList, so it's
not that slow, nor that memory inefficient, but if you need to push
the limits in terms of performances or memory, you'd better write a
specific container perfectly adapted to your needs.
Anyway, any feedback is welcome, as always, even if my coding
philosophy is a bit controversial :)
--
jice
jice
>
> I didn't say anything about its quality, it seems pretty good;
Yeah, but "beginner user friendly" is often associated with "low
quality stuff" in people's mind. And unfortunately, most of the time,
it's true... ;)
--
jice
jice
> On 15 juil, 03:22, stu <yakumo9...@gmail.com> wrote:
>
>
> > I think the list code is low quality compared to the rest of TCOD,
> > your using for loops to move large chunks of contiguous memory
> > around, thats plain lazy when you can just memmove and be done.
>
>
> aaarghing, but there won't be any noticeable change in the programs
> using TCODList :P
>
On a second thought, I won't do it, because I've just seen that
memmove handle memory overlapping by copying the data from the source
to a temporary array, then from the temporary array to the
destination. This is even worse than my simple loop...
--
jice
zai...@zaimoni.com
> On a second thought, I won't do it, because I've just seen that
> memmove handle memory overlapping by copying the data from the source
> to a temporary array,
Sounds like you're looking at a catastrophically bad implementation.
Even on machines that don't have a block-data-copy assembly
instruction, memmove should require only a (unsigned) char temporary.
On machines that do, a competent implementation memcpy should use it
(and in Intel's case, a competent implementation of memmove should use
it as well).
> then from the temporary array to the destination. This is even worse than my simple loop...
Actually, since the memory chunks in TCODList should be non-
overlapping, you could get away with memcpy.
Ray Dillinger
> On a second thought, I won't do it, because I've just seen that
> memmove handle memory overlapping by copying the data from the source
> to a temporary array, then from the temporary array to the
> destination. This is even worse than my simple loop...
Are you sure? I thought it just switched the direction of its iteration,
IE, started copying at the "top" of the memory areas rather than at the
"bottom." If it behaves as you say, I'd consider it a priority 7 bug*.
In commercial environments priority 7 bugs never get fixed. In freeware
environments it depends on how much it annoys somebody to know that such
a petty bug is there and fixable.
Bear
Priority 7: Code is obviously linearly suboptimal, ie, runs some
constant factor slower or uses some constant factor
more memory than it has to, and the fix is both
obvious and easy.
jice
> On Jul 15, 4:56 am, jice <jice.nos...@gmail.com> wrote:
>
> > On a second thought, I won't do it, because I've just seen that
> > memmove handle memory overlapping by copying the data from the source
> > to a temporary array,
>
> Sounds like you're looking at a catastrophically bad implementation.
Xubuntu 8.04 manpage...
>
> > then from the temporary array to the destination. This is even worse than my simple loop...
>
> Actually, since the memory chunks in TCODList should be non-
> overlapping, you could get away with memcpy.
In the case of the insertion, they are overlapping.
Ok there's no need talking forever, I'll time 1 million insertions
with lib 1.3.2 and with a modified version using memmove and I keep
the faster. But as I said, it doesn't matter, nobody will ever use it
to insert 1 millions elements ;P
--
jice
jice
>
> Ok there's no need talking forever, I'll time 1 million insertions
> with lib 1.3.2 and with a modified version using memmove and I keep
> the faster. But as I said, it doesn't matter, nobody will ever use it
> to insert 1 millions elements ;P
>
Ok here are the results. I ran the tests with mingw32 programs
compiled with -O3 flag. I ran each test 3 times and I report here the
average time on the 3 runs. I'm using the new constructor allowing to
preallocate the memory to time only the insertion. I timed 3
scenarios : 10 000 insertions, 100 000 insertions and 200 000
insertions.
The test source code for 200 000 iterations :
int main()
{
TCODList<int> l(200000);
float start=TCODSystem::getElapsedSeconds();
for (int i=200000;i!=0;i--) {
l.insertBefore(i,0);
}
float end=TCODSystem::getElapsedSeconds();
printf("elapsed : %g sec",(end-start));
return 0;
}
The results :
For 10 000 insertions :
for loop : 0.12 s
memmove : 0.73 s
For 100 000 insertions :
for loop : 15.1 s
memmove : 14.4 s
For 200 000 insertions :
for loop : 72.3 s
memmove : 65.5 s
I could run the test on Linux too, but I really don't care. Switching
to memmove is not worth before 100 000 insertions. I can think of no
list in a roguelike that would contains 100 000 elements. Most of them
contains only a few dozens elements. I keep the for loop.
--
jice
Joni Toivanen
> Ok here are the results. I ran the tests with mingw32 programs
> compiled with -O3 flag. I ran each test 3 times and I report here the
> average time on the 3 runs. I'm using the new constructor allowing to
> preallocate the memory to time only the insertion. I timed 3
> scenarios : 10 000 insertions, 100 000 insertions and 200 000
> insertions.
>
> The test source code for 200 000 iterations :
> int main()
> {
> TCODList<int> l(200000);
> float start=TCODSystem::getElapsedSeconds();
> for (int i=200000;i!=0;i--) {
> l.insertBefore(i,0);
> }
> float end=TCODSystem::getElapsedSeconds();
> printf("elapsed : %g sec",(end-start));
> return 0;
> }
[Snip the results]
Note that you can probably get much more accurate results if you use
something like the 'time' command on a Linux system (I'm sure there is
something similar for other operating systems too). It will measure the
actual time used by the program, and not the elapsed time (which is not
reliable, because your system might be doing something on the background
and skew the results).
No comments on the actual comparison, though, as I was pretty much
expecting this result :)
Joni Toivanen
> On 15 juil, 18:57, zaim...@zaimoni.com wrote:
>> On Jul 15, 4:56 am, jice <jice.nos...@gmail.com> wrote:
>>
>> > On a second thought, I won't do it, because I've just seen that
>> > memmove handle memory overlapping by copying the data from the source
>> > to a temporary array,
>>
>> Sounds like you're looking at a catastrophically bad implementation.
>
> Xubuntu 8.04 manpage...
>
In that case, I believe you misread the manpage. It actually says:
"copying takes place as though the bytes in src are first copied into a
temporary array that does not overlap src or dest".
Notice the usage of "as though".
At least the libc implementation on my Linux system does use the
"block-data" assembler instructions, but that doesn't actually matter
that much on modern processors (as your test in the other post shows),
because these days processors can run simple, predictable loops
extremely fast (and most likely it would be limited more by memory
bandwidth than processor speed, anyway).
Ido Yehieli
> In that case, I believe you misread the manpage. It actually says:
> "copying takes place as though the bytes in src are first copied into a
> temporary array that does not overlap src or dest".
>
> Notice the usage of "as though".
>
> At least the libc implementation on my Linux system does use the
> "block-data" assembler instructions, but that doesn't actually matter
> that much on modern processors (as your test in the other post shows),
> because these days processors can run simple, predictable loops
> extremely fast (and most likely it would be limited more by memory
> bandwidth than processor speed, anyway).
This is probably insignificant in terms of performance even a 10 years
old cpu (which btw will give us a pentium III these days), but using
memmove isn't more difficult than using a loop. In fact it is even
easier, provided you know about the existence of that function :)
Ido Yehieli
> The results :
> For 10 000 insertions :
>
> for loop : 0.12 s
> memmove : 0.73 s
>
> For 100 000 insertions :
>
> for loop : 15.1 s
> memmove : 14.4 s
>
> For 200 000 insertions :
>
> for loop : 72.3 s
> memmove : 65.5 s
>
> I could run the test on Linux too, but I really don't care. Switching
> to memmove is not worth before 100 000 insertions. I can think of no
> list in a roguelike that would contains 100 000 elements. Most of them
> contains only a few dozens elements. I keep the for loop.
For a few dozens elements it wouldn't make a difference if you used a
method that is 1000 times slower than both combined. Performance is a
none issue in this case.
jice
> jice wrote:
> > On 15 juil, 18:57, zaim...@zaimoni.com wrote:
> >> On Jul 15, 4:56 am, jice <jice.nos...@gmail.com> wrote:
>
> >> > On a second thought, I won't do it, because I've just seen that
> >> > memmove handle memory overlapping by copying the data from the source
> >> > to a temporary array,
>
> >> Sounds like you're looking at a catastrophically bad implementation.
>
> > Xubuntu 8.04 manpage...
>
> In that case, I believe you misread the manpage. It actually says:
> "copying takes place as though the bytes in src are first copied into a
> temporary array that does not overlap src or dest".
>
I'm reading the french man page, and apparently, the translation
sucks. Here is what it says when I re-translate it to english :
"The memmove function copies n bytes from the src memory block to the
dest memory block. The two blocks can overlap : the src block is first
copied in a temporary array, then the temporary array is copied to
dest."
--
jice
jice
> jice wrote:
> > Ok here are the results.
>
>
> Note that you can probably get much more accurate results if you use
> something like the 'time' command on a Linux system (I'm sure there is
> something similar for other operating systems too). It will measure the
> actual time used by the program, and not the elapsed time (which is not
> reliable, because your system might be doing something on the background
> and skew the results).
>
Right, except that time will take the process start and the list
memory allocation into account. While it may not matter for the last
test, it could definitely screw the 10 000 and 100 000 insertions
tests as the difference between both tests is less than 1 sec.
--
jice
jice
>
> At least the libc implementation on my Linux system does use the
> "block-data" assembler instructions, but that doesn't actually matter
> that much on modern processors (as your test in the other post shows),
> because these days processors can run simple, predictable loops
> extremely fast (and most likely it would be limited more by memory
> bandwidth than processor speed, anyway).
This whole thread confirm me in my opinion on optimization. My advice
would be :
Never think about optimization before you have a performance issue.
Write the most simple, most straightforward code as possible as it
will be more readable, more maintainable, and who knows, it could even
be faster !
--
jice
Ido Yehieli
> This whole thread confirm me in my opinion on optimization. My advice
> would be :
>
> Never think about optimization before you have a performance issue.
> Write the most simple, most straightforward code as possible as it
> will be more readable, more maintainable, and who knows, it could even
> be faster !
True, but I think the argument has now moved on to "use a standard
library function instead of rolling your implemntation, unless you
have a good reason not to". In this particular instance implementing
your own is just very easy.
-Ido.
konijn_
I wonder though, since you are not using a realistic use case ( a
hardcoded 200000 in a loop ), did the compiler optimize the bejeezus
out of it ?
Could you do memmove a favour and just put that in a function that
accepts the count ?
The optimization in that case would be more realistic and I wonder if
the results would be different.
Cheers,
T.
>
> --
> jice
jice
>
> > On 15 juil, 19:43, jice <jice.nos...@gmail.com> wrote:
>
> > The test source code for 200 000 iterations :
> > int main()
> > {
> > TCODList<int> l(200000);
> > float start=TCODSystem::getElapsedSeconds();
> > for (int i=200000;i!=0;i--) {
> > l.insertBefore(i,0);
> > }
> > float end=TCODSystem::getElapsedSeconds();
> > printf("elapsed : %g sec",(end-start));
> > return 0;
>
> > }
>
>
> hardcoded 200000 in a loop ), did the compiler optimize the bejeezus
> out of it ?
>
> Could you do memmove a favour and just put that in a function that
> accepts the count ?
> The optimization in that case would be more realistic and I wonder if
> the results would be different.
>
I think you didn't get it. The memmove or for loop are inside the
insertBefore function. There's no point putting the test loop in a
function. Moreover, we already wasted too much time on this.
--
jice
konijn_
> > I wonder though, since you are not using a realistic use case ( a
> > hardcoded 200000 in a loop ), did the compiler optimize the bejeezus
> > out of it ?
>
> > Could you do memmove a favour and just put that in a function that
> > accepts the count ?
> > The optimization in that case would be more realistic and I wonder if
> > the results would be different.
>
> I think you didn't get it.
Ouch. ;)
The memmove or for loop are inside the
> insertBefore function. There's no point putting the test loop in a
> function. Moreover, we already wasted too much time on this.
Good enough.
>
> --
> jice