Şu linkteki optimizasyonu incelerken gözüme çarpması üzerine;
"ForEachAround" bu hot path içinde çalışan bir func, bir bakayım dedim üstün zekalı YMIR geliştiricileri neighbor list'i iterate ediyor functor içinde.
"m_neighbor_list" bu bir std::list yani doubly linked list implementasyonu, ne yapıyor bu? "SECTREE_MAP::Build" fonksiyonunda yani harita yüklenirken içine en fazla 9 tane komşu (kendisi + 8 komşu) pushlanıyor ve sadece read-only iterate olarak kullanılmış, build'den sonra hiç sattei değişmiyor.
Şimdi akış şöyle: ForEachAround, UpdateSectree üzerinden hareket/spawn/teleport/state-değişimi gibi olaylarda tetikleniyor, her tickte değil ama bir hot path sayılabilir. N entity x en fazla 9 komşu desek baya bir pointer chasing + indirection maliyeti var. Zaten böyle bir senaryoda neden std::list tercih edersin ki? iterator invalidation ihtimali yok, reallocation derdin yok çünkü sadece tabiri caizse initialize aşamasında bir şeyler pushluyorsun.
-> komşu sayısı load time'da sabitleniyor(üst sınır 9 fonksiyona bakarsınız gözümden kaçtıysa daha fazla olabilir ama yok gibi)
-> doubly linked listin herhangi bir faydası kullanılmıyor (ortaya ekleme vs o(1), no memory reallocation vb.)
e o zaman neden std::list tercih edilmiş? bunun cevabı gerçekten Allah bilir, hiçbir mantıklı sebebi yok.
trick burdaki container seçimini düzeltip contiguous bir container (std::vector ya da sabit kapasiteli boost::container::static_vector, std::inplace_vector vb.) tercih edin. Tabii sonuçları ölçmeden performans kazancı olduğunu kimse iddia edemez mantıken toplam çağrı sayısı arttıkça falan faydası görülmeli, ölçün.
Elde edilecek faydalar:
No pointer chasing
ILP
bla bla bla. klasik cache locality faydaları.
"ForEachAround" bu hot path içinde çalışan bir func, bir bakayım dedim üstün zekalı YMIR geliştiricileri neighbor list'i iterate ediyor functor içinde.
C++:
FCollectEntity collector;
#ifdef __clang__
LPSECTREE_LIST::const_iterator it = m_neighbor_list.begin();
#else
LPSECTREE_LIST::iterator it = m_neighbor_list.begin();
#endif
for ( ; it != m_neighbor_list.end(); ++it)
{
LPSECTREE sectree = *it;
sectree->for_each_entity(collector);
}
collector.ForEach(func);"m_neighbor_list" bu bir std::list yani doubly linked list implementasyonu, ne yapıyor bu? "SECTREE_MAP::Build" fonksiyonunda yani harita yüklenirken içine en fazla 9 tane komşu (kendisi + 8 komşu) pushlanıyor ve sadece read-only iterate olarak kullanılmış, build'den sonra hiç sattei değişmiyor.
Şimdi akış şöyle: ForEachAround, UpdateSectree üzerinden hareket/spawn/teleport/state-değişimi gibi olaylarda tetikleniyor, her tickte değil ama bir hot path sayılabilir. N entity x en fazla 9 komşu desek baya bir pointer chasing + indirection maliyeti var. Zaten böyle bir senaryoda neden std::list tercih edersin ki? iterator invalidation ihtimali yok, reallocation derdin yok çünkü sadece tabiri caizse initialize aşamasında bir şeyler pushluyorsun.
-> komşu sayısı load time'da sabitleniyor(üst sınır 9 fonksiyona bakarsınız gözümden kaçtıysa daha fazla olabilir ama yok gibi)
-> doubly linked listin herhangi bir faydası kullanılmıyor (ortaya ekleme vs o(1), no memory reallocation vb.)
e o zaman neden std::list tercih edilmiş? bunun cevabı gerçekten Allah bilir, hiçbir mantıklı sebebi yok.
trick burdaki container seçimini düzeltip contiguous bir container (std::vector ya da sabit kapasiteli boost::container::static_vector, std::inplace_vector vb.) tercih edin. Tabii sonuçları ölçmeden performans kazancı olduğunu kimse iddia edemez mantıken toplam çağrı sayısı arttıkça falan faydası görülmeli, ölçün.
Elde edilecek faydalar:
No pointer chasing
ILP
bla bla bla. klasik cache locality faydaları.