Page MenuHomeWildfire Games

Change internals of EntityMap to use an std:: vector
ClosedPublic

Authored by wraitii on Dec 26 2016, 3:10 PM.

Details

Reviewers
temple
Group Reviewers
Restricted Owners Package(Owns No Changed Paths)
Commits
rP22029: Change internals of EntityMap to use an std::vector
Summary

Ported over from http://trac.wildfiregames.com/ticket/4347

EntityMap, our fast replacement for std::map<entity_id_t, V> was coded by RedFox. As such, it's weird. It uses a C-like buffer, and is generally not very nice.
Attached patch replaces all that with an std::vector and removes the "inline" everywhere and generally makes it nicer. Also adds a "start ID" information to avoid having a useless invalid member in front.
I also add tests (I believe I've got 100% coverage) and test performance.
(NB: the patch keeps the old entity map for purposes of performance comparisons (it's never worse, perhaps even better), obviously that would not get into svn).

Test Plan

Verify that tests pass, review new coding, test a game and check for a similar hash.

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
leper added inline comments.Mar 28 2017, 11:47 AM
source/simulation2/system/EntityMap.h
30

Ah, right.

This revision now requires changes to proceed.Mar 28 2017, 11:47 AM
wraitii updated this revision to Diff 2426.EditedJun 4 2017, 5:35 PM
wraitii edited edge metadata.
wraitii marked 2 inline comments as done.

Fixed your comments and explicited a few things.

source/simulation2/system/EntityMap.h
88

Forgot to remove this, I prefer the constructor approach over the conversion approach but could be persuaded otherwise.

92

Unsure how you'd do that, templating on return type clang says he can't infer what i'm talking about. Reluctant for SFINAE trickery here if it allows it.

114

This doesn't actually return end, it just starts the whole "skipping" loop in _iter, so we return the first valid element.

Does warrant a comment.

161–163

this was actually safe since we always have a valid ID at the end for iterator loop safety, but I've made that more explicit and I've removed those -1 anyways.

Vulcan added a comment.Jun 4 2017, 6:00 PM
Executing section Default...
Executing section Source...

source/simulation2/system/EntityMap_old.h
|  89| »   »   »   return·ptr;
|    | [MAJOR] CPPCheckBear (returnReference):
|    | Reference to auto variable returned.
Executing section JS...
Executing section XML GUI...
Executing section Python...
Executing section Perl...

http://jw:8080/job/phabricator_lint/127/ for more details.

Vulcan added a comment.Jun 4 2017, 9:44 PM

Build has FAILED

Updating workspaces.
Build (release)...
In file included from ../../../source/simulation2/tests/test_EntityMap.cpp:17:0:
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h: In member function ‘void TestEntityMap::test_insert()’:
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:43:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(1,1);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:44:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(2,2);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:45:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(3,3);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:46:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(4,4);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:47:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(4,5);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:48:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(4,6);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:56:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(10,7);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:70:9: error: ‘class EntityMap<int, 5u>’ has no member named ‘insert’
   test2.insert(8,5);
         ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h: In member function ‘void TestEntityMap::test_iterators()’:
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:80:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(1,1);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:81:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(2,2);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:82:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(3,3);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:83:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(4,4);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:110:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(10,1);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:111:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(20,2);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:112:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(30,3);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:113:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(40,4);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h: In member function ‘void TestEntityMap::test_erase()’:
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:129:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(1,1);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:130:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(2,2);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:131:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(3,3);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:132:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(4,4);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:149:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(1,1);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:150:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(2,2);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:151:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(3,3);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:152:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(4,4);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h: In member function ‘void TestEntityMap::test_clear()’:
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:166:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(1,1);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:167:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(2,2);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:168:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(3,3);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:169:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(4,4);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h: In member function ‘void TestEntityMap::test_find()’:
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:180:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(1,1);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:181:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(2,2);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:182:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(3,3);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:183:8: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
   test.insert(40,4);
        ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h: In member function ‘void TestEntityMap::test_perf()’:
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:197:9: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
    test.insert(i,i);
         ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:209:9: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
    test.insert(i,i);
         ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:232:9: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
    test.insert(i,i);
         ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:249:9: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
    test.insert(i*5,i);
         ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:260:9: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
    test.insert(i*50,i);
         ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:271:9: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
    test.insert(i*50,i);
         ^
/mnt/data/jenkins-phabricator/workspace/phabricator/source/simulation2/tests/test_EntityMap.h:282:9: error: ‘class EntityMap<int, 1u>’ has no member named ‘insert’
    test.insert(i*50,i);
         ^
make[1]: *** [obj/test_Release/test_EntityMap.o] Error 1
make: *** [test] Error 2
make: *** Waiting for unfinished jobs....

Link to build: http://jw:8080/job/phabricator/1474/
See console output for more information: http://jw:8080/job/phabricator/1474/console

wraitii updated this revision to Diff 2466.Jun 7 2017, 6:15 PM

Forgot about the tests…

leper requested changes to this revision.Jun 7 2017, 6:30 PM
leper added inline comments.
source/simulation2/system/EntityMap.h
58

That should most likely be a compile time assertion.

75

I'm not sure whether we omit braces for do-while loops (not that we have lots of those).

I guess while ((++val)->first == INVALID_ENTITY)\n\t; would work too, not sure if that is easier to read, maybe a for loop would work, dunno.

88

Current approach is fine by me, unless someone else has another opinion.

123

Not quite the same parameters as std::map, but not sure if we should bother.

125–126

Even if we'd re-use this, we still need to make sure the keys are valid (which in this case is just this ensure).

126

ENSURE(

147

The iterator variant of erase doesn't return size_t.

source/simulation2/tests/test_EntityMap.h
1

I suspect you want to update this.

100

...

193

Why iostreams? Also why do you explicitly flush the output stream twice?

196

I somewhat dislike for loops with <= since they are very likely to be off-by-one errors and cause out-of-bounds reads/writes. (Not an issue here, but still.)

(Same for the others below.)

This revision now requires changes to proceed.Jun 7 2017, 6:30 PM
Vulcan added a comment.Jun 7 2017, 7:03 PM

Build is green

Updating workspaces.
Build (release)...
Build (debug)...
Running release tests...
Running cxxtest tests (318 tests)....................................
Testing performance of old EntityMap
Inserting 200K elements in order: 0.00367672s
Erasing 200K elements, by key: 0.000557664s
Inserting 200K elements in reverse order: 0.00101943s
Erasing 200K elements, by iterator: 0.000676576s
Erasing 200K non-existing elements: 0.000577231s
200K random lookups in random order: 0.00160076s
auto iteration on 200K continuous entitymap: 0.000575711s
auto iteration on 200K sparse (holes of 5): 0.00289949s
auto iteration on 4K sparse (holes of 50): 0.00243846s
auto iteration on 200K sparse (holes of 50): 0.0253158s
.........................................................
Testing performance of EntityMap
insert_or_assigning 200K elements in order: 0.00794601s
Erasing 200K elements, by key: 0.000710711s
insert_or_assigning 200K elements in reverse order: 0.000920502s
Erasing 200K elements, by iterator: 0.000435339s
Erasing 200K non-existing elements: 0.000702555s
200K random lookups in random order: 0.00185039s
auto iteration on 200K continuous entitymap: 0.000592136s
auto iteration on 200K sparse (holes of 5): 0.00284607s
auto iteration on 4K sparse (holes of 50): 0.000298533s
auto iteration on 200K sparse (holes of 50): 0.0203731s
manual ++iteration on 2000K sparse (holes of 50) (warmup 1): 0.20188s
manual iteration++ on 2000K sparse (holes of 50) (warmup 2): 0.271824s
manual ++iteration on 2000K sparse (holes of 50): 0.245108s
manual iteration++ on 2000K sparse (holes of 50): 0.273644s
.................................................................................................................................................................................................................................OK!
Running debug tests...
Running cxxtest tests (318 tests)....................................
Testing performance of old EntityMap
Inserting 200K elements in order: 0.00843697s
Erasing 200K elements, by key: 0.00381889s
Inserting 200K elements in reverse order: 0.00457237s
Erasing 200K elements, by iterator: 0.0104035s
Erasing 200K non-existing elements: 0.00247015s
200K random lookups in random order: 0.00987224s
auto iteration on 200K continuous entitymap: 0.00351678s
auto iteration on 200K sparse (holes of 5): 0.00654461s
auto iteration on 4K sparse (holes of 50): 0.00475831s
auto iteration on 200K sparse (holes of 50): 0.0518322s
.........................................................
Testing performance of EntityMap
insert_or_assigning 200K elements in order: 0.133009s
Erasing 200K elements, by key: 0.0252206s
insert_or_assigning 200K elements in reverse order: 0.0273015s
Erasing 200K elements, by iterator: 0.0455368s
Erasing 200K non-existing elements: 0.0166832s
200K random lookups in random order: 0.0144933s
auto iteration on 200K continuous entitymap: 0.00359811s
auto iteration on 200K sparse (holes of 5): 0.00934396s
auto iteration on 4K sparse (holes of 50): 0.00133774s
auto iteration on 200K sparse (holes of 50): 0.0522003s
manual ++iteration on 2000K sparse (holes of 50) (warmup 1): 0.595964s
manual iteration++ on 2000K sparse (holes of 50) (warmup 2): 0.6179s
manual ++iteration on 2000K sparse (holes of 50): 0.60217s
manual iteration++ on 2000K sparse (holes of 50): 0.624296s
.................................................................................................................................................................................................................................OK!
Checking XML files...

http://jw:8080/job/phabricator/1501/ for more details.

Vulcan added a comment.Jun 7 2017, 7:04 PM
Executing section Default...
Executing section Source...

source/simulation2/system/EntityMap_old.h
|  89| »   »   »   return·ptr;
|    | [MAJOR] CPPCheckBear (returnReference):
|    | Reference to auto variable returned.
Executing section JS...
Executing section XML GUI...
Executing section Python...
Executing section Perl...

http://jw:8080/job/phabricator_lint/148/ for more details.

wraitii updated this revision to Diff 3998.Oct 28 2017, 7:01 PM
wraitii marked 25 inline comments as done.

RC

source/simulation2/system/EntityMap.h
125–126

Right, not sure why I wrote that actually

147

while true, our iterator may point to an invalid entity and not erase anything so I'm keeping it this way.

source/simulation2/tests/test_EntityMap.h
193

Lazyness on both counts.

Build is green

Updating workspaces...
Build (release)...
Build (debug)...
Running release tests...
Running cxxtest tests (307 tests)...................................................................................................................................................................................................................................................................................................................OK!
Running debug tests...
Running cxxtest tests (307 tests)...................................................................................................................................................................................................................................................................................................................OK!
Checking XML files...

http://jenkins-master:8080/job/phabricator/2177/ for more details.

Executing section Default...
Executing section Source...
Executing section JS...

http://jenkins-master:8080/job/phabricator_lint/641/ for more details.

leper added inline comments.Oct 29 2017, 3:57 AM
source/simulation2/system/EntityMap.h
112

Is there anything that actually prevents us from running past end()?

128

at the en_d_.

I guess this partially answers my question above.

140

Why not ++m_Count?

173

Could probably be const.

wraitii updated this revision to Diff 4014.Oct 29 2017, 2:19 PM
wraitii marked 10 inline comments as done.

Address comments.

source/simulation2/system/EntityMap.h
112

Yup, ITERATOR_GATE above, added a comment.

140

no reason.

173

This makes clang complain that "functions that differ only on their return type cannot be overloaded".

I can't think of an easy way around that.

source/simulation2/tests/test_EntityMap.h
191

Meant to disable this one for perf reasons

wraitii marked an inline comment as done.Oct 29 2017, 2:20 PM
wraitii added inline comments.
source/simulation2/tests/test_EntityMap.h
191

Done now but I messed up the name, will fix before committing if this gets accepted.

Build is green

Updating workspaces...
Build (release)...
Build (debug)...
Running release tests...
Running cxxtest tests (312 tests)........................................................................................................................................................................................................................................................................................................................OK!
Running debug tests...
Running cxxtest tests (312 tests)........................................................................................................................................................................................................................................................................................................................OK!
Checking XML files...

http://jenkins-master:8080/job/phabricator/2187/ for more details.

Executing section Default...
Executing section Source...
Executing section JS...

http://jenkins-master:8080/job/phabricator_lint/643/ for more details.

wraitii added a reviewer: Restricted Owners Package.Nov 1 2017, 6:01 PM
wraitii marked an inline comment as done.

I'll commit this shortly unless somebody complains.

leper resigned from this revision.Nov 11 2017, 8:53 PM
leper edited reviewers, added: Itms; removed: leper.
In D8#40273, @wraitii wrote:

I'll commit this shortly unless somebody complains.

$complaint

How about actually getting someone to review your patches instead of trying to blackmail people into doing so?

(One could complain about the strange loop style used in the tests, but meh.)

In D8#40273, @wraitii wrote:

I'll commit this shortly unless somebody complains.

It would be better indeed that someone officially accepts the patch. leper did find some things with the code but that's not a complete review. Did you try asking on IRC whether @echotangoecho or @temple are interested in taking a look at that engine patch? If you have some time ?

source/simulation2/system/EntityMap.h
180

What about removing this instance of the method? The method itself should be const but the iterator should be usable without restrictions, and initializing a const_iterator with a regular one is not an issue. This would also prevent exact code duplication in the two overloads.

186

I can't help but thinking this is a media scandal involving iterators!

I don't have any expertise here, so I'll pass.

I did not, I bumped it with the above message, which on this diff and another has successfully gotten some attention. Don't see it as "blackmailing", see it as "crying out for help".

source/simulation2/system/EntityMap.h
186

I think I was going for "Fence" but got my words confused, actually.

wraitii updated this revision to Diff 4368.Nov 25 2017, 3:34 PM
wraitii removed a reviewer: Itms.

Rename ITERATOR_GATE to ITERATOR_FENCE as that's the right name for it.

This comment was removed by wraitii.

Successful build - Chance fights ever on the side of the prudent.

Updating workspaces...
Build (release)...
Build (debug)...
Running release tests...
Running cxxtest tests (313 tests).........................................................................................................................................................................................................................................................................................................................OK!
Running debug tests...
Running cxxtest tests (313 tests).........................................................................................................................................................................................................................................................................................................................OK!
Checking XML files...
Executing section Default...
Executing section Source...
Executing section JS...
In D8#42149, @wraitii wrote:

Rename ITERATOR_GATE to ITERATOR_FENCE as that's the right name for it.

Sentinel might be the word you are looking for.

wraitii updated this revision to Diff 5398.Jan 21 2018, 5:25 PM

Bump year for the second time. If the clock strikes 2020 I'm committing this anyways.

wraitii edited reviewers, added: temple; removed: Restricted Owners Package.May 5 2018, 3:59 PM
wraitii updated this revision to Diff 7257.Jan 5 2019, 11:59 AM

Clarify head comment and revert the test-dumbing-down from D1722. The changes are strictly cosmetic.

Build failure - The Moirai have given mortals hearts that can endure.

Link to build: https://jenkins.wildfiregames.com/job/differential/916/

wraitii updated this revision to Diff 7274.Jan 5 2019, 5:38 PM

Reupload to run on SVN now that tests have been merged.

Vulcan added a comment.Jan 5 2019, 6:18 PM

Successful build - Chance fights ever on the side of the prudent.

Linter detected issues:
Executing section Source...

source/simulation2/components/CCmpRangeManager.cpp
|   1| /*·Copyright·(C)·2018·Wildfire·Games.
|    | [NORMAL] LicenseYearBear:
|    | License should have "2019" year instead of "2018"
Executing section JS...
Executing section cli...

Link to build: https://jenkins.wildfiregames.com/job/differential/924/

This revision was not accepted when it landed; it landed in state Needs Review.Jan 5 2019, 7:20 PM
This revision was automatically updated to reflect the committed changes.