text: Posts: 236
  Registered: 02-05
  Posts: 11776
  Registered: 07-06
  Last edited by Maes on 10-13-12 at 19:01
  Posts: 932
  Registered: 04-09
  Posts: 7625
  Registered: 01-03
  Optimus said:
  GZdoom: Another strange thing. Before even waking monsters, whether I am looking towards them or away to the wall, frame rate is quite low, like 20fps (lower than Zdoom even when looking). Only when I went very close to the wall and only facing a single bonus item (the grey 200 health/armor sphere) suddenly it went up to 200. Strange. Maybe it's because of how they are handled in OpenGL, possibly regardless they are in your view or not, the quads are sent to the graphics card and let it zbuffer them automatically? And maybe even not with the most optimized way for the GPU to do this.
  Posts: 280
  Registered: 11-06
  Maes said:
  When the projectiles start flying....it's a memory allocation fuckfest of mobj_t's getting constantly created & destroyed.
  Last edited by wesleyjohnson on 10-19-12 at 02:13
  Posts: 5757
  Registered: 08-00. When adding a new mobj_t, I grab the last deleted pointer, use that slot, then decrement the "deleted pointer" pointer, if you know what I mean. It's extremely fast. The only realloc occurs when the block needs to grow. Don't know if this scheme is very popular - I haven't seen it before, but I'm quite proud of it :).
  Graf Zahl said:
  What kind of graphics card do you have?
  The big problem with sprites is that due to some translucency at the edges they need to be pre-sorted and drawn in order.
  I never had any problems with this on NVidia but I have been told that ATI/AMD doesn't like it when it has to draw lots of stuff with constant state changes.
  Quasar said:
  This is called a free list and is a common method for amortizing the cost of malloc/free - question: do you have any conclusive profilings that show an overall consistent improvement from this?
  Quasar said:
  I ask because I have thought about doing this for Eternity many times in the past but decided not to do it because I felt it would be difficult to strike a balance with memory usage - I don't think it's really appropriate to let the free list grow to an indefinite size, for example.
  Graf Zahl said:
  Using it for a structure as large as a mobj_t in Doom is certainly not a good idea. First, they do not get allocated frequently enough - not even in Nuts.wad and second, they are hogging a lot of memory which would make normal heap use less efficient.
  code:
  //
  // [kb] Fast mobj allocation/removal that does not use Z_Malloc. Mobjs
  // are always the same size in memory, so this code allocates a block of
  // memory dedicated to mobjs. When exhausted, a new block is allocated.
  // A separate FIFO list of deleted mobjs is also maintained, and is
  // used to handle requests for new mobjs. Unitl the delete list
  // becomes empty, all new allocations will overwrite previously
  // removed mobjs.
  //
  #define FASTMOBJ_SPAWNBLOCKSIZE 4096
  #define FASTMOBJ_DELETEBLOCKSIZE 4096
  mobj_t **fastmobjblocks = NULL;
  int fastmobjblock_index = 0;
  int fastmobjblock_alloc = 0;
  int fastmobj_index = 0;
  mobj_t **fastmobjdeletes = NULL;
  int fastmobjdelete_index = 0;
  int fastmobjdelete_alloc = 0;
  void P_FastMobj_Init (void)
  {
  int i;
  if (fastmobjblock_alloc)
  {
  for (i = 0; i <= fastmobjblock_index; i++)
  {
  free(fastmobjblocks[i]);
  fastmobjblocks[i] = NULL;
  }
  free(fastmobjblocks);
  fastmobjblocks = NULL;
  fastmobjblock_index = 0;
  fastmobjblock_alloc = 0;
  fastmobj_index = 0;
  }
  if (fastmobjdelete_alloc)
  {
  free(fastmobjdeletes);
  fastmobjdeletes = NULL;
  fastmobjdelete_alloc = 0;
  fastmobjdelete_index = 0;
  }
  P_ClearTmThing();
  }
  mobj_t *P_AllocFastMobj (void)
  {
  if (fastmobjdelete_index)
  {
  fastmobjdelete_index--;
  return (mobj_t *) fastmobjdeletes[fastmobjdelete_index];
  }
  if (fastmobj_index >= FASTMOBJ_SPAWNBLOCKSIZE)
  {
  fastmobjblock_index++;
  fastmobj_index = 0;
  }
  if (fastmobjblock_index >= fastmobjblock_alloc)
  {
  fastmobjblock_alloc++;
  fastmobjblocks = realloc(fastmobjblocks, fastmobjblock_alloc * sizeof(mobj_t *));
  fastmobjblocks[fastmobjblock_index] = malloc(sizeof(mobj_t) * FASTMOBJ_SPAWNBLOCKSIZE);
  }
  return (mobj_t *)&(fastmobjblocks[fastmobjblock_index][fastmobj_index++]);
  }
  void P_DeallocFastMobj(mobj_t *mobj)
  {
  if (fastmobjdelete_index >= fastmobjdelete_alloc)
  {
  fastmobjdelete_alloc += FASTMOBJ_DELETEBLOCKSIZE;
  fastmobjdeletes = realloc(fastmobjdeletes, fastmobjdelete_alloc * sizeof(mobj_t *));
  }
  fastmobjdeletes[fastmobjdelete_index++] = mobj;
  }
  kb1 said:
  I then modified the ZMalloc code to try a little harder to find free space. Even though it had more searching to do, it appeared to work better, faster, and cycle much less, given the same conditions.
  Unsatisfied, I did the aforementioned approach - the "freelist". Man, what a difference that made - the heap stopped cycling altogether. See, the real benefit is that you're taking the thing that would wreak havoc on the heap (mobj_t allocations), and getting it out of the heap altogether. That lets the ZMalloc code do the only thing it's really designed well to do - load "static" pre-level objects, like textures, sounds, flats, etc.
  Graf Zahl said:
  ...stuff...
  wesleyjohnson said:
  Flying missiles last for at least a few seconds, so I expect the missile turnover per frame to be a reasonable load.
  Last edited by Maes on 10-23-12 at 02:33
  kb1 said:
  The point is that, combining media data with mobj_t's in the same heap is demonstrably problematic, without a brilliant allocator. Hell, the Boom allocator purges textures on each heap cycle, whether there's free space or not. Doom's does too. They just loop around happily stomping whatever's there, assuming that it'll just get reloaded, no big deal - heh. The low-memory scenario I consturcted was simply to make the heap activity as hectic as possible, and, to then observe the effects of the freelist. I design empirically. That bothers some people - so be it. I like to see the "real-world" effect of my changes, not just theorize about them.
  Graf Zahl said:
  No, I know precisely what you did.
  Graf Zahl said:
  But if you want to get useful data you cannot use results from fringe cases as a benchmark to test against.
  If you want to know how much real improvement you get from your freelist you got to use a testing pattern that's at least realistic.
  And deliberately running on low memory conditions to worsen performance is not realistic.
  Graf Zahl said:
  Also, testing a freelist against a known bad implementation doesn't show the superiority of the freelist either, it merely demonstrates that the bad implementation performs badly.
  Graf Zahl said:
  Of course the freelist performs better, there's not even need to demonstrate it - but that's not due to the greatness of the freelist but due to the badness of Doom's zone heap.
  Graf Zahl said:
  To get the real value of the freelist you still need to test it against a sane heap system with sufficient memory.
  Graf Zahl said:
  The ultimate question should be: How much improvement would switching to malloc/free bring, compared to the freelist?
  Graf Zahl said:
  And more importantly, how much are the improvements in relation to overall execution time?
  Graf Zahl said:
  And sorry, but my tests in this matter done years ago showed that:
  - designing a heap that doesn't thrash is the most important thing of all.
  - If you want to run maps that need lots of memory, use a system that's up to it. Even Doom.exe, despite being able to run with 4MB of heap didn't do too well. It needed 8 MB to avoid the constant disc accesses. It just needed to support 4MB to lower system requirements on the packaging.
  - with the above taken into account, allocation and deallocation is more or less insignificant in relation to the other things being done. With lots of mobj_t's around the main bottleneck is mostly the movement/collision detection code.
  Graf Zahl said:
  The big problem with a freelist is that ultimately it requires more memory than proper handling of deallocation of these objects. You end up with (peak of mobj_t) + (peak of everything else) instead of peak of (mobj_t + everything else). (which makes testing against low memory conditions that induce thrashing even more meaningless.)
  Maes said:
  Out of curiosity, I fucked around a bit with my old mobj_t pool code. To my surprise, it did work without problems, only that it didn't give any measurable speed advantage (on the opposite, it caused some minor degradation, due to being forced to do a class checking before submitting a "dead" object back to the queue).
  I was able to offset that by allocating more than one new object when the pool was empty, but still, it maybe gained a frame or so in speed. No difference in heap memory use either (around 72 MB for nuts.wad in either case) which means that Java is still comfortable enough to defer garbage collection. It might make more of a difference in a constrained memory scenario, where the GC will be forced to work overtime.
  Posts: 2053
  Registered: 08-03
  kb1 said:
  Yeah, I know - I provided source, and a description.
  What's not realistic? It really happened. What suggests to you that I did not test hundreds of patterns? I already explained that the low memory condition caused increased heap cycling, which is precisely the condition that is alleviated when using the freelist. The low memory condition makes things apparent faster - 1 minute vs. 20.
  Why on earth do you think I sought a solution in the first place? Just cause I wanted to fuck around with things? It's because I noticed an effect that was undesirable - in normal playing conditions.
  kb1 said:
  Malloc is a "black box", whose performance characteristics can only be measured empirically. Sure, OSes/language compilers do their best, and have some pretty smart people writing them, but the best performance is gained when you don't make the call at all.
  kb1 said:
  Sorry, double-post. Yeah, I forgot to suggest that the mobj_t needs to be zeroed first, I thought that might have been what caused you problems the first time.
  Last edited by Maes on 10-24-12 at 10:53
  Maes said:
  In the working version of the code, I noticed that I didn't do any particular zeroing except maybe for the function codepointer. TBQH I don't remember what the actual issue was, however it seems solved now :-/
  DaniJ said:
  I just want to point out a contextual difference between where Graf is coming from and you (kb1) and Maes are - in ZDoom (and it's derivatives) a mobj_t is not a single fixed size. In his port a mobj_t instance is a dynamic composition, inheriting from (potentially) several different base classes.
  Maes said:
  In the working version of the code, I noticed that I didn't do any particular zeroing except maybe for the function codepointer. TBQH I don't remember what the actual issue was, however it seems solved now :-/
  Quasar said:
  I feel it should be noted that establishment of rigorous referential integrity is an obvious prerequisite.
  code:
  memset(mobj, 0, sizeof(*mobj));
  info = &mobjinfo[type];
  mobj->type = type;
  mobj->info = info;
  etc.
  Graf Zahl said:
  (things in a respectful manner)
  Graf Zahl said:
  So...
  As I pointed out, you have a higher peak because you got 2 distinctive blocks of memory, which both need to be able to keep the maximum required amount of RAM.
  Graf Zahl said:
  If you run out of memory in such situations, keeping a freelist would inevitably mean you allocate more memory - because you need to keep all the freed objects' memory allocated.
  Graf Zahl said:
  So, why not increase the heap's size to begin with?
  Graf Zahl said:
  Seriously, the first thing I'd do with Doom these days is dump the zone heap.
  Graf Zahl said:
  Uh... Sorry, no. This may have been the case in days long past, but with modern CPUs and memory caching on the CPU it's not that easy. Your freelist *may* be better, yet again it may not. It depends a lot on memory usage patterns.
  Graf Zahl said:
  Also, micro-optimization, meaning you optimize code that only runs less than 1% of the entire execution time will bring no realistic speed improvement at all...The only exception I have to make is when a significant number of very small objects gets frequently allocated and deallocated...And by frequent I mean something like several hundreds of these that get thrown away in the same frame normally.
  Maes said:
  ...but the code changed a lot since them, and I didn't commit the unsuccessful attempts.
  This in turn triggered me to complete a proper "codepointer" system with rewirable per-mobj "function pointers".
  kb1 said:
  You can place "valid REJECT map building" in this category as well. I wish people would spend the small amount of extra time it takes to do this - it's almost always a win.
  Graf Zahl said:
  Is it?
  Here's a better idea: Use a faster sight checking algorithm! And the good news: It already exists in the form of the Doom 1.2 version!
  Graf Zahl said:
  Sure, I could see that it took a tiny few milliseconds less - but as I said, using the alternative sighr checking code even without REJECT provided much better performance improvement.
  >