[RESOLVED] Condition::Contains implementation

Programmers discuss here anything related to FreeOrion programming. Primarily for the developers to discuss.

Moderator: Committer

Message
Author
User avatar
cami
Space Dragon
Posts: 411
Joined: Tue Sep 20, 2011 10:32 pm
Location: Halle (Saale)

Re: Condition::Contains implementation

#31 Post by cami »

tzlaine wrote:Looking at those numbers again. it seems that all of the difference between list and vector is coming from insert and erase, not copying.
Please note that copying is still implemented by insertion atm.
tzlaine wrote: I also notice that your adapter is doing a lot more than "push_back()" and "*it = back(); pop_back()", respectively. This leads me to believe that an adapter-free implementation using vector might be faster than both the adapter-based ones.
What do you mean in particular? I believe that's exactly what I do, just I have to check whether it already is the last element, and I strictly follow the random access container + sequence model (r.a. alone cannot be resized) instead of using the BackInsertionSequence methods. I also need to return an iterator to the inserted or past the erased element for proper iteration. Note that std::vector stores the "begin" and "end" pointers internally, and everything else is computed from that.

The loop-free adaptor methods are certainly fully inlined by the compiler, though I didnt verify that. I'd rather place some inlining hints here than manually inline the code, we already have enough duplicates of ConditionBase::Eval(). In fact, I politely refuse to inline all the adapter code manually :þ I'm convinced it's futile, error-prone and hard to maintain.Image
Attachments
angry.gif
angry.gif (9.48 KiB) Viewed 2245 times
Yesterday, we were still on the brink. Fortunately, today we have come one step further.

User avatar
cami
Space Dragon
Posts: 411
Joined: Tue Sep 20, 2011 10:32 pm
Location: Halle (Saale)

Re: Condition::Contains implementation

#32 Post by cami »

I tried to squeeze the last cpu cycle out of the adapter now. It seems that the extra running time came from the algorithm change in ConditionBase::Eval and its cousins and my sub-optimal adaptor implementation (or missing inlining?). I also made a test run with 8K items preallocated in the adaptor constructor (the universe in the test game contains between 3k and 4k items I believe). To my surprise, it hardly had any effect on running time at all. I included an extra column for malloc() to show that allocation doesn't play a major role. I omitted memcpy as it was below 0.05% in all tests.

Code: Select all

___container___|_total_|_insert_|_erase_|_malloc_
           set | 100.0 |  43.4  |  4.1  |   .3
          list |  61.6 |   6.9  |  1.0  |   .3
        vector |  59.6 |   5.2  |  1.6  |   .1
vector+reserve |  59.5 |   4.9  |  1.6  |   .1
std::set (gzipped, 3.1MB)
std::list (gzipped, 3.2MB)
std::vector (gzipped, 3.2MB)
std::vector, preallocated (gzipped, 3.2MB)
Attachments

[The extension patch has been deactivated and can no longer be displayed.]

Yesterday, we were still on the brink. Fortunately, today we have come one step further.

tzlaine
Programming Lead Emeritus
Posts: 1092
Joined: Thu Jun 26, 2003 1:33 pm

Re: Condition::Contains implementation

#33 Post by tzlaine »

cami wrote:In fact, I politely refuse to inline all the adapter code manually :þ I'm convinced it's futile, error-prone and hard to maintain.Image
I think we have different views on what maintainability means. I understand that you don't want to make the same kind of change in a bunch of places, but I put to you that explicit is better than implicit if you want to make code more maintainable. Using an adapter when we don't strictly need to is obscure. It means that a line of code that appears to be using a std::set is actually using a std::vector via an adapter. This kind of aliasing makes maintenance more difficult in the long run. If you don't know (or even don't remember) that you're actually dealing with a std::vector, you might do something stupid like do a find() on the "set" in a loop, introducing a O(N*N) slowdown without realizing it. This kind of problem is particularly bad for new developers, who must do some spelunking to figure out that the code they're looking at doesn't do what it looks like it does.

If you don't want to make those changes, I don't mind doing it.

User avatar
cami
Space Dragon
Posts: 411
Joined: Tue Sep 20, 2011 10:32 pm
Location: Halle (Saale)

Re: Condition::Contains implementation

#34 Post by cami »

Well, I hoped the emote showed this was a half-joke. I didn't plan to keep the adapter code, but I planned to make ObjectSet a real class adhering the Multiple Simple Associative Container interface (but not running time constraints). I could also choose names suggesting the real computation costs better than the concept's names, for instance scan(key) instead of find(key) or erase_all(key) instead of erase(key), if you prefer. Then, if you want to shove the pointers into your contributors' faces, well, I understand that, it'll just take quite some time and -at least if I do it- thorough testing, as I tend to make (and overlook) lots of mistakes in repetitive work.

Off topic: It's certainly obvious to you that I've a rather generic programming style introducing a substantial amount of complexity, it's mimicking my way of thinking. I thought that'd match the project as you use some quite generic code, especially where you interface with boost which drives universality to the extreme. I have my bad experiences with both : complexity and duplicate code. In the long run, both approaches seem to have the same effect of hampering software evolution, one by lack of code flexibility, the other by lack of code transparency. It's the software maintainer's task to balance between the two, according to the project's requirements and the team's capabilities. Personally, I can tackle complexity much better than inflexibility, that's why I generally tend in this direction.
Last edited by cami on Fri Oct 07, 2011 2:42 pm, edited 1 time in total.
Yesterday, we were still on the brink. Fortunately, today we have come one step further.

User avatar
Geoff the Medio
Programming, Design, Admin
Posts: 13587
Joined: Wed Oct 08, 2003 1:33 am
Location: Munich

Re: Condition::Contains implementation

#35 Post by Geoff the Medio »

If there's no dramatic improvement in run time with erasing from a vector by using a bare overwrite-with-end()-1 and pop, would it be worth considering future parallelization suitability to pick between vector and list?

Most Condition filtering of sets of objects presumably should easily be split into two or more independent subsets to be handled in separate threads, where presently Eval loops over the whole set, matching each element. Is there any significant difference in difficulty between vector and list in splitting the input set and merging the result?

AFAIK neither container is thread-safe, so just using iterator ranges into the input container would not work. Instead, both would need to be split into two separate containers for independent processing and merged back later.

As far as I can tell, there's no way to use a std::list::iterator to split a std::list into two independent lists in constant time (new list's first element being that iterator's, and old list's last element being the one before it). This is surprising t me, and would have been useful for this purpose...
cami wrote:...I planned to make ObjectSet a real class adhering the Multiple Simple Associative Container interface (but not running time constraints). I could also choose names suggesting the real computation costs better than the concept's names, for instance scan(key) instead of find(key) or erase_all(key) instead of erase(key), if you prefer.
I think you mentioned something about it already, but does ObjectSet actually need a full container interface? What operations are done on it besides begin(), end(), erase(iterator), clear(), insert(key), and insert(iterator, iterator)?

User avatar
cami
Space Dragon
Posts: 411
Joined: Tue Sep 20, 2011 10:32 pm
Location: Halle (Saale)

Re: Condition::Contains implementation

#36 Post by cami »

STL is thread-safe in the following sense: data structures can be shared read-only safely, and the same functions/methods can be called on different data structures (different variables of the same type) simultaneously. This is the best you can achieve without noticeable performance penalties. The non-destructive interface would help us here: threads could share method input, but use private output which is merged when methods complete. Boost offers means for thread synchronisation so that variables can be manipulated by different threads concurrently, however I wouldn't recommend such an approach, lock contention can eat up a significant portion of the gain, if not slow down in the end.

Since in near future, cpu parallelism won't exceed the number of effects in FreeOrion, I'd say it's not worth considering anything more than computing different effects in parallel. That doesnt require any splitting or merging, just a little scheduling in Effect target set computation.

If you really want to go as far as parallelizing on the subcondition evaluation level, std::list can be merged and split in constant time using std::list<>::splice(). Splitting requires an iterator pointing to the middle of the list. std::vector can be merged and split in linear time, but with a very low constant factor, using memcpy(). Experiments are necessary to verify who is the winner for our set sizes. I would have bet for std::list but my intuition has failed on freeorion several times now so I don't trust it in this case =)

P.S. IIRC The following methods are used on Condition::ObjectSet and/or Effect::TargetSet:

insert(value)
insert(iterator, value)
insert(iterator range)
insert(iterator, iterator range)
find(key)
erase(iterator)
erase(key)

Since the adaptor is throw-away code, I didnt waste time implementing anything that's not needed for the tests. I'm unsure about the positioned insertions, they might be required only by my own adapter code. I omitted anything defined in the (Forward) Container concept, as it will be inherited from any container implementation anyways.
I'll precise my earlier statement in that I intended to implement the adapter's interface, which is actually pretty close to multiple simple associative container, the remaining functionality provided by the underlying STL container class.
Yesterday, we were still on the brink. Fortunately, today we have come one step further.

User avatar
Geoff the Medio
Programming, Design, Admin
Posts: 13587
Joined: Wed Oct 08, 2003 1:33 am
Location: Munich

Re: Condition::Contains implementation

#37 Post by Geoff the Medio »

cami wrote:Since in near future, cpu parallelism won't exceed the number of effects in FreeOrion, I'd say it's not worth considering anything more than computing different effects in parallel. That doesnt require any splitting or merging, just a little scheduling in Effect target set computation.
That's probably a better idea.
The following methods are used on Condition::ObjectSet and/or Effect::TargetSet:
Where are find(key) and erase(key) used?

tzlaine
Programming Lead Emeritus
Posts: 1092
Joined: Thu Jun 26, 2003 1:33 pm

Re: Condition::Contains implementation

#38 Post by tzlaine »

cami wrote:Well, I hoped the emote showed this was a half-joke. I didn't plan to keep the adapter code, but I planned to make ObjectSet a real class adhering the Multiple Simple Associative Container interface (but not running time constraints). I could also choose names suggesting the real computation costs better than the concept's names, for instance scan(key) instead of find(key) or erase_all(key) instead of erase(key), if you prefer. Then, if you want to shove the pointers into your contributors' faces, well, I understand that, it'll just take quite some time and -at least if I do it- thorough testing, as I tend to make (and overlook) lots of mistakes in repetitive work.
I new you were joking about being angry, but I thought you were serious about not wanting to make the changes. I meant no offense, I was just explaining my take on maintainability (there are certainly a lot of differing ones around).
Off topic: It's certainly obvious to you that I've a rather generic programming style introducing a substantial amount of complexity, it's mimicking my way of thinking. I thought that'd match the project as you use some quite generic code, especially where you interface with boost which drives universality to the extreme. I have my bad experiences with both : complexity and duplicate code. In the long run, both approaches seem to have the same effect of hampering software evolution, one by lack of code flexibility, the other by lack of code transparency. It's the software maintainer's task to balance between the two, according to the project's requirements and the team's capabilities. Personally, I can tackle complexity much better than inflexibility, that's why I generally tend in this direction.
I struggle with this too, believe me. I think anyone who really thinks hard about programming on a large scale in c++ does. I have drifted steadily away from flexibility as a goal, towards simplicity. I find that in the long run, and in most cases, simplicity provides a better kind of flexibility in application code (library code is another matter...). Being overly general often introduces so much code that maintenance becomes an issue, and the generality written into the original implementation often turns out to be a mistaken guess about the future direction of the code. YMMV.

tzlaine
Programming Lead Emeritus
Posts: 1092
Joined: Thu Jun 26, 2003 1:33 pm

Re: Condition::Contains implementation

#39 Post by tzlaine »

cami wrote:std::list can be merged and split in constant time using std::list<>::splice().
FWIW, this is true for GNU, but not MS. In c++11's STL, it will not be true for any conforming implementation.

User avatar
cami
Space Dragon
Posts: 411
Joined: Tue Sep 20, 2011 10:32 pm
Location: Halle (Saale)

Re: Condition::Contains implementation

#40 Post by cami »

Can you please explain your abbreviations :mrgreen: Nah don't bother, I looked them up.
When talking about STL, I'm always referring to SGI's (latest) version. Individual implementations may differ slightly, of course. I'm not sure where you got the information about C++11 from, though, cppreference.com even shows extensions of the splice() feature for c++11.

Geoff: I believe somewhere in Effects.cpp or maybe Universe.cpp. Look for the method name you'll quickly find them. or apply the patch, remove their implementations and watch the compilation errors =) Condition.cpp doesn't use them.

Off topic: Trying to anticipate future changes is almost always a bad idea (sometimes you have seen the same change several times before and its likely to happen again). When I said general code, I meant low coupling code, in this case, keeping the assumptions about the ObjectSet implementation low. Oh well.
Yesterday, we were still on the brink. Fortunately, today we have come one step further.

tzlaine
Programming Lead Emeritus
Posts: 1092
Joined: Thu Jun 26, 2003 1:33 pm

Re: Condition::Contains implementation

#41 Post by tzlaine »

cami wrote:I'm not sure where you got the information about C++11 from, though, cppreference.com even shows extensions of the splice() feature for c++11.
std::list can have an O(1) size() or an O(1) splice(), but not both (because it's impossible to have both). c++03 allows implementations to pick which one they want to implement as O(1) (SGI and GNU picked size(), MS picked slice()). c++11 requires O(1) size() for all containers, implying that slice() is always O(N) in c++11.

User avatar
cami
Space Dragon
Posts: 411
Joined: Tue Sep 20, 2011 10:32 pm
Location: Halle (Saale)

Re: Condition::Contains implementation

#42 Post by cami »

Ah, there is the rub! Well, there's probably a portable list implementation out there that chooses the other one, and if not, it'd be embarassingly easy to create one. Fortunately, we don't need one in the first place. It's late in Germany, so I'll call it a day. =)

Update: really too much work for my time available.
Note that pop_back() invalidates all iterators on a vector. Either you'll have to inline the erase(p) code from the adaptor or you will need to switch from iterators to indices and lose a few cycles again.

It seems Condition.cpp uses find() as well. That said, the adaptor probably didnt work correctly for algorithms like:

Code: Select all

it = find(key)
if (it != end()) {
    do_something(key)
    erase(it)
}
because it didnt model a unique (associative) container.

Code: Select all

found = false;
for (int i=0; i < size(); ) {
    if (at(i) == key) {
        found = true;
        at(i) = back(); pop_back();
    } else ++i;
}
if(found) do_something(key)
It's a bummer I have no tools that can inline source code.
Yesterday, we were still on the brink. Fortunately, today we have come one step further.

User avatar
Geoff the Medio
Programming, Design, Admin
Posts: 13587
Joined: Wed Oct 08, 2003 1:33 am
Location: Munich

Re: Condition::Contains implementation

#43 Post by Geoff the Medio »

cami wrote:It seems Condition.cpp uses find() as well.
Indeed, though I can't find "find(" anywhere in Effect.cpp. The uses of std::set::find in SortedNumberOf and a function it calls, TransferSortedObjects, aren't essential, though; they can be adapted to work with a list by scanning through it with std::find, or perhaps std::find_if while making use of a predicate that checks if the item being tested is suitably placed in the sorted map of objects, instead of iterating through the sorted list and finding the objects in the ObjectSet as is done now.

tzlaine
Programming Lead Emeritus
Posts: 1092
Joined: Thu Jun 26, 2003 1:33 pm

Re: Condition::Contains implementation

#44 Post by tzlaine »

A form of Carsten's approach, using std::vector directly, including calls to reserve(), is now in SVN. Out of curiosity, I took only the simple-match branches of Condition::*::Eval() and replaced it with a version of what Carsten describes on the first page of this thread. Instead of getting new numbers to test, I got a really nasty crash (I had to reboot). I'm not sure if I messed something up when making my patch, but if not, I don't think the don't-erase-from-from_set strategy is going to work. Patch attached.
Attachments

[The extension patch has been deactivated and can no longer be displayed.]


User avatar
cami
Space Dragon
Posts: 411
Joined: Tue Sep 20, 2011 10:32 pm
Location: Halle (Saale)

Re: Condition::Contains implementation

#45 Post by cami »

Unfortunately, it's not as simple as that. You can't just keep the potentially unused target list unchanged and hope everything works. First, we currently don't know which list will be actually used because of Not. Second, there might be situations where both are actually used. All Conditions need to be rewritten to conform to the new interface, they need to exploit it, there's no point just plugging it in when it doesn't fit. Especially supporting the old destructive interface requires special attention, because the seach space will also be one of the target containers (matches or non matches).

I currently dont have time to code, unfortunately, but there is no way to quickly test this. We can measure the amount of copying (I did earlier in this thread), and implementing this will eleminate all copying, that's the data we have.
Yesterday, we were still on the brink. Fortunately, today we have come one step further.

Post Reply