DLL development discussions

[Koshling]

Yup. Totally agree.
But I'm actually quite sensitive about words "guarantied", "sure", "100%". People who use them incorrectly in small cases, tend to use them incorrectly in big cases also. For the rest I do not have strength to write today...

Back to the heap. -- The big lose in the space repeats something like once per 7 seeds. For 5 there is more or less 60MB lost. And for 1, 5-10. Checked also for 2 000 000 of operations. The losses were smaller, but the proportion of allocated and lost numbers of MB looked the same. In bad cases there was even over 200MB per 400-500 allocated.

For me it doesn't look good. But maybe I'm tired.

Well, if you think you can improve on it, go for it is all I can say. With Civ we're stuck with a system running in an environment that is somewhat fixed by the EXE, and has to interact with a black box whose behavior can only be inferred from poking i! (the game engine). That often leaves experimentation as the only practical way to determine whether something can actually be useful done, and I'd say you've done the useful background research now, and it sounds like that suggests there may be potential for useful changes. The next step is to try it experimentally (possibly in a quick&dirty way just to validate the principal, and then hon it once the principal proves itself in real game numbers)

 

[n47]

With Civ we're stuck with a system running in an environment that is somewhat fixed by the EXE, and has to interact with a black box whose behavior can only be inferred from poking i! (the game engine).

It is good you reminded me this. In the approach I've been thinking of, the place object in the memory may change -- probably not too usual -- so I am wondering will the engine cope with it. If it would take a pointer to an object inside itself and access though it, it could end badly. But if it would do something like this, it could end badly even now, if I understand thing correctly, as the object could be deleted during this.

Is it right?

edit
Oh, and what sizes of objects are involved in the mass storage? Can we say they are <100B? (I mean shallow data - like sizeof(obj) )

 

[Koshling]

It is good you reminded me this. In the approach I've been thinking of, the place object in the memory may change -- probably not too usual -- so I am wondering will the engine cope with it. If it would take a pointer to an object inside itself and access though it, it could end badly. But if it would do something like this, it could end badly even now, if I understand thing correctly, as the object could be deleted during this.

Is it right?

edit
Oh, and what sizes of objects are involved in the mass storage? Can we say they are <100B? (I mean shallow data - like sizeof(obj) )

Some objects are passed to the engine, and in some cases allocation and deletion even happen on opposite sides of the barrier (which is why the engine API provides an allocator you're supposed to use for any memory new'd/delete'd in that way). However, this does not apply to anything allocated via the FFreeTrashList mechanism, so those can be modified as you see fit. It's probably mostly just CvString and CvWString in fact though there are a few cases where objects are added (in the DLL) to std::vectors controlled by the engine, so the allocators for those are constrained to just use 'new' (those cases are rare though, and localized so you're unlikely to accidentally impact one of them).

As to sizeof(object instance) for the Cv... classes - more like 1K than 100 bytes, but definitely < 10K. If you write a new allocator just instrument it to get accurate stats from real gameplay. I **think** CvCity is the biggest, but CvUnit probably runs it close.

 

[n47]

more like 1K than 100 bytes, but definitely < 10K

Holly sh*t! They surely should go on a diet. You aren't holding buildings as some bit array, are you? But still, from what I remember in my game there were something below 200 removals per turn. Even if it would get 10 times more frequent, if we would not remove this objects immediately, once per turn, we would have <20MB lost. Or is there a chance that objects will be removed even more often?

From this, depends how to optimize the structure. I can do it, that a single pointer will be enough to dereference an object, but then the object's memory will not be deallocated immediately on the removal. Or I can use a double pointer and remove the object immediately -- approach like what we have now. I'm wondering, what is more important for us: 20MB or probably much smaller peak memory lose and faster object access, or the opposition? -- I have a feeling, both are equally insignificant, but can't decide myself.

 

[Koshling]

Holly sh*t! They surely should go on a diet. You aren't holding buildings as some bit array, are you? But still, from what I remember in my game there were something below 200 removals per turn. Even if it would get 10 times more frequent, if we would not remove this objects immediately, once per turn, we would have <20MB lost. Or is there a chance that objects will be removed even more often?

From this, depends how to optimize the structure. I can do it, that a single pointer will be enough to dereference an object, but then the object's memory will not be deallocated immediately on the removal. Or I can use a double pointer and remove the object immediately -- approach like what we have now. I'm wondering, what is more important for us: 20MB or probably much smaller peak memory lose and faster object access, or the opposition? -- I have a feeling, both are equally insignificant, but can't decide myself.

Building (instances) are indeed an array in the CvCity object, but since cities have an appreciable faction of all buildings in a mature game (which is when memory matters most), that's not actually inefficient per se (the actual implementation however is a bit, because it holds a count which is just an int, but actually only takes very small values, which strictly could be represented in quite a few less bits), and anyway, there are only a few hundred city objects in an entire game, so it's a small percentage of total usage.

A better example (and concern) is promotions in a CvUnit instance, because there are orders of magnitude more unit instances than city instances, and promotions on unit are very analogous to buildings on cities (indeed so much so that I would make them all generic base classes of essentially property modifier bags if I were writing the game from scratch). Because of the scale of units we rewrote that aspect of the CvUnit structure to remove the array of size(num possible promotions) [actually several such arrays!], and replace it with a sparse list of applied promotion infos.

 

[Nimek]

In Unit info you don't have to hold Info about all promos that unit have but only info about highest promotions per promotio line.

It could be associative array where key is promotion line Id and value is integer.
Number of elements in array will depends on number of promos from different promotion line that unit has.

 

[n47]

and replace it with a sparse list of applied promotion infos.

You mean sparse array implemented with linked list? Would it be significantly smaller? In one pointer we have already space for 32 promotions. If we would have 160 promotions it would take 20 bytes. And I believe we can strongly minimize it, by splinting ranges of promotions for land, water, air, spy, general units. I think non of those classes can have even half of all promotions, so we would have 10 bytes per unit. And with something similar to what Nimek said, we could reduce it to something like ... maybe 8?

Btw, have you read PM?

 

[Koshling]

In Unit info you don't have to hold Info about all promos that unit have but only info about highest promotions per promotio line.

It could be associative array where key is promotion line Id and value is integer.
Number of elements in array will depends on number of promos from different promotion line that unit has.

It is just such an associative array

 

[n47]

Ow my, Koshling again don't want to talk to me. Have I again said something about patting, which I can't recall due to my advanced age?

 

[JosEPh_II]

@n47,
koshling pops in and out, he'll respond. He posted earlier this week about needing to get some "real life programming/work" done too.

JosEPh

 

[Koshling]

Ow my, Koshling again don't want to talk to me. Have I again said something about patting, which I can't recall due to my advanced age?

I had read the PM and I thought I had responded since then. Which post have I not responded to that you feel I should have done?

 

[Koshling]

You mean sparse array implemented with linked list? Would it be significantly smaller? In one pointer we have already space for 32 promotions. If we would have 160 promotions it would take 20 bytes. And I believe we can strongly minimize it, by splinting ranges of promotions for land, water, air, spy, general units. I think non of those classes can have even half of all promotions, so we would have 10 bytes per unit. And with something similar to what Nimek said, we could reduce it to something like ... maybe 8?

Btw, have you read PM?

It's not just a flag, it's also state that is required to be associated with the instances of some promotions on their owning unit. This is mostly combat mod stuff associated with affliction promotions. Strictly only a minority of promotion instances actually need more state storing than their presence, so the sparse entries (sparse in promotion space) could themselves be sparse in state-space (currently they are not). However, going for the second level of sparseness at the expense of complexity gets into diminishing returns, so while this could be done (and would save circa 30 bytes / promotion instance) it hasn't currently. In a large game (say 100000 units with 5 or so promotions each) the potential is to save of the order of 15M, which is not terribly significant in the grand scheme of things (but neither is it utterly trivial, so this wouldn't be a ridiculous thing to optimize)

 

[n47]

@Koshling

[...]there were something below 200 (object) removals per turn. Even if it would get 10 times more frequent [...] we would have <20MB lost. Or is there a chance that objects will be removed even more often?

I can do it, that a single pointer will be enough to dereference an object, but then the object's memory will not be deallocated immediately on the removal. Or I can use a double pointer and remove the object immediately -- approach like what we have now. I'm wondering, what is more important for us: 20MB or probably much smaller peak memory lose and faster object access, or the opposition? -- I have a feeling, both are equally insignificant, but can't decide myself.

 

[Koshling]

@Koshling

The double indirection (essentially replace pointers with handles) approach is cleaner IMO. If it's worth doing at all I'd opt for that approach.

 

[n47]

Done.
From some preview testing the performance looks like
- 3.3x faster then FFreeListTrashArray
- 3% less space for adding-reading operation chain
- 31% less space for adding-removing-reading operation chain (with average 1 removal per 3 additions)

Btw, also noticed, after deleting FFreeListTrashArray there still remains a reserved shared virtual memory piece of the size comparable to that allocated by objects on heap. Any ideas?

Yup, yup, I know, we care little about the time in this case. But maybe we can get some memory saving. I believe, we have some removals from FFreeListTrashArray, don't we?

 

[Nimek]

@n47

In later gameplay how much your changes speeds up turn times?

 

[Koshling]

Done.
From some preview testing the performance looks like
- 3.3x faster then FFreeListTrashArray
- 3% less space for adding-reading operation chain
- 31% less space for adding-removing-reading operation chain (with average 1 removal per 3 additions)

Btw, also noticed, after deleting FFreeListTrashArray there still remains a reserved shared virtual memory piece of the size comparable to that allocated by objects on heap. Any ideas?

Yup, yup, I know, we care little about the time in this case. But maybe we can get some memory saving. I believe, we have some removals from FFreeListTrashArray, don't we?

Sounds good. The objects themselves were never allocated in the FFreeListTrashArray structure, just pointers to them:

	m_pArray[iIndex].pData = new T;
	m_pArray[iIndex].iNextFreeIndex = FFreeList::INVALID_INDEX;

so presumably you've removed (much of) the overhead of the tracking array structure, but the objects themselves are still on the normal heap.

 

[n47]

@n47

In later gameplay how much your changes speeds up turn times?

How much do they speed up? Sweet Lord, I'm not Flash! I haven't injected this structure into the dll, yet. First of all, this thing is critical, so it has to be damn well tested in the fist place. And also the old structure have many references in the code so it will take some time to refactor it.

But, if you think about this 3.3x, I can already ensure you, that you will not even see a change. This thing is not the point. The point may be in this, it can reduce paging. -- I do not know, how it looks like for guys with 4GB RAM, but for my 2, paging take a hell lot of time.

@Koshling, how, if the destructor calls uninit and this calls removeAll, which has

	for (iI = 0; iI < m_iNumSlots; iI++)
	{
		m_pArray[iI].iNextFreeIndex = FFreeList::INVALID_INDEX;
		if (m_pArray[iI].pData != NULL)
		{
			delete m_pArray[iI].pData;
		}
		m_pArray[iI].pData = NULL;
	}

Besides, private virtual memory is disposed and I thought the heap should be there.

OK, tomorrow I'll test more. Let's hope it will still work.

 

[Koshling]

How much do they speed up? Sweet Lord, I'm not Flash! I haven't injected this structure into the dll, yet. First of all, this thing is critical, so it has to be damn well tested in the fist place. And also the old structure have many references in the code so it will take some time to refactor it.

But, if you think about this 3.3x, I can already ensure you, that you will not even see a change. This thing is not the point. The point may be in this, it can reduce paging. -- I do not know, how it looks like for guys with 4GB RAM, but for my 2, paging take a hell lot of time.

@Koshling, how, if the destructor calls uninit and this calls removeAll, which has

	for (iI = 0; iI < m_iNumSlots; iI++)
	{
		m_pArray[iI].iNextFreeIndex = FFreeList::INVALID_INDEX;
		if (m_pArray[iI].pData != NULL)
		{
			delete m_pArray[iI].pData;
		}
		m_pArray[iI].pData = NULL;
	}

Besides, private virtual memory is disposed and I thought the heap should be there.

OK, tomorrow I'll test more. Let's hope it will still work.

Maybe I'm not following what you're asking. The deletes in the loop above are the deletes of the individual objects (units etc), each one individually allocated on the heap previously. However, the destructor for the entire managing structure is only called when the containing object (player mostly) is destructed. Typically this happens only on game exit or (un)load.

 

[n47]

@Koshling, sure, but I do not say, it is a problem for us. I am wondering, why something like this happens, at all. In my test unit the trasharray is deleted before exit and the tests stops to show statistics, so I could observe it.