c++ - avoid cache miss related to 1:N relationship in entity-component-system -
how avoid cache miss related 1:n (pirateship-cannon) relationship in entity-component-system (ecs)?
for example, pirateship can have 1-100 cannons. (1:n)
each cannon can detach/attach freely pirateship @ time.
for reasons, pirateship , cannon should entity.
memory diagram
in around first time-steps, when ship/cannon gradually created, ecs memory looks nice :-
image note:
- left = low address, right = high address
- although there seems gaps,
shipcom,cannoncomcompact arrays.
it fast access cannon information ship , vice versa (pseudo code):-
ptr<shipcom> shipcom=....; entityptr ship = shipcom; //implicitly conversion array<entityptr> cannons = getallcannonfromship(ship); for(auto cannon: cannons){ ptr<cannoncom> cannoncom=cannon; //cannoncom-> .... } problem
in later time-step, ship / cannon randomly created/destroyed.
result, entity,shipcom , cannoncom array has gap scattering around.
when want allocate them, random memory block pool.
entityptr ship = ..... (an old existing ship) entityptr cannon = createnewentity(); ptr<cannoncom> cannoncom= createnew<cannoncom>(cannon); attach_pirate_cannon(ship,cannon); //^ ship entity , cannon tend have different (far-away) address thus, "really fast" code above become bottom-neck. (i profiled.)
(edit) believe underlying cache miss occur different address between cannon inside same ship.
for example (@ address of turret component),
shipahasturret@01turret@49shipbhasturret@50turret@99
in later timesteps, if turret@99 moved shipa, :-
shipahasturret@01turret@49+turret@99(mem jump)shipbhasturret@50turret@98
question
what design pattern / c++ magic reduce cache miss frequently-used relation?
more information:
- in real case, there lot of 1:1 , 1:n relationship. relationship binds type of component type of component.
- for example,
relation_pirate_cannon = (shipcom:cannoncom),relation_physic_graphic = (physiccom:graphiccom) - only of relation "indirect" often.
- current architecture has no limit on amount of
entity/shipcom/cannoncom.
don't want restrict in beginning of program. - i prefer improvement not make game-logic coding harder.
the first solution come mind enable relocation, believe last resort approach.
a possible solution add layer of indirection. slows things down bit, helps keeping compact arrays , speeding whole thing. profiling way know if helps.
that being said, how that?
here brief introduction sparse set , it's worth reading before proceed better understand i'm saying.
instead of create relationships between items within same array, use second array point.
let's call 2 arrays reverse , direct:
- reverse accessed through entity identifier (a number, index in array). each , every slot contains index within direct array.
- direct accessed, well... directly , each slot contains entity identifier (that index access reverse array) , actual component.
whenever add cannon, entity identifier , first free slot in direct array. set slot.entity entity identifier , put in reverse[entity] index of slot. whenever drop something, copy last element in direct array keep compact , adjust indexes relationships hold up.
ship store indexes outer array (reverse), free switch , forth things within inner array (direct).
what advantages , disadvantages?
well, whenever access cannons through outer array, have jump because of layer of indirection. anyway, long succeed in keeping low number of accesses made way , visit direct array in systems, have compact array iterate , lowest number of cache misses.
Comments
Post a Comment