TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

Avoiding game crashes related to linked lists

133 点作者 adj超过 12 年前

14 条评论

Negitivefrags超过 12 年前
Before you consider intrusive lists, in fact, before you consider almost any other data structure, try a vector.<p>People grossly overestimate the cost of vector relocation while underestimating the benefits of cache coherency. Vector relocation is so cheap because all the bits are in the cache. You can relocate all the elements in a reasonably sized vector faster than you can dereference a pointer to somewhere in memory that isn't in cache.<p>If you want log(n) lookup like a set/map you can keep the vector sorted. If you want fast erase (and don't care about order) you can move the last element to the middle and resize down by one (no memory allocation).<p>The &#60;algorithm&#62; header makes these operations trivial.<p>C++11 move semantics mean that there are a lot of types you can keep by value in a vector that you wouldn't have before and they stay fast.
评论 #4499985 未加载
评论 #4498751 未加载
评论 #4498741 未加载
评论 #4498986 未加载
评论 #4498629 未加载
beder超过 12 年前
There's plenty of discussion relating to the article he references at <a href="http://news.ycombinator.com/item?id=4455225" rel="nofollow">http://news.ycombinator.com/item?id=4455225</a>, and much of the same applies here.<p>1. He's not comparing apples-to-apples between `std::list` and his intrusive linked list; the proper analogue would be to unlink a node from its iterator, for which the running time is still O(1).<p>2. The main (only?) reason to use intrusive lists is for the single indirection (which helps both memory and speed). In his example for how using std::list would crash his server because of the O(N) node removal, he's just not storing the right data for each connection (again, use an iterator).<p>3. He looked at boost's intrusive list, but I'm guessing he didn't actually try it out. The examples are pretty good, and it's much easier than it "looks". (That is, boost libraries can look intimidating when you first look at them because they're so template-heavy.)<p>4. It may even be that a vector, plus an auxiliary data structure for lookup, may be faster.
评论 #4498754 未加载
评论 #4498732 未加载
eps超过 12 年前
Ah, the potent mix of the offsetof and C++. It takes one junior dev to sprinkle a bit of inheritance on top and wonderous things will start happening in your crash-proof code. In other words, it takes much more displine to use embedded data containers instead of embedding ones, the C-style discipline, which is clearly not for everyone.
kev009超过 12 年前
What's funny is he mentions the ZMQ in C entries as an impetuous but then essentially writes the list the way any novice C programmer _would_ (vs. expert/"leet" C++ prgorammers from the article). To me, this unwittingly plays into the "why ZMQ would be better in C" meme far more than the other way around :o)<p>See also &#60;sys/queue.h&#62;.
评论 #4498683 未加载
pubby超过 12 年前
The reason this guy thinks std::list is buggy is because he's using it incorrectly. There's not reason to write removal functions like delete_person when they already exist with list::remove, list::erase, find, search, etc. There's no reason to use std::list&#60;foo*&#62; either when std::list&#60;foo&#62; and std::list&#60;std::unique_ptr&#60;foo&#62;&#62; work just as well.<p>His example code is very dubious as it looks like C-with-classes rather than C++, mostly due to the lack of RAII.<p>Intrusive lists are still worth knowing and using, it's just that the author's reasoning was terrible. I found the Boost.Intrusive page to be much more knowledgeable: <a href="http://www.boost.org/doc/libs/1_35_0/doc/html/intrusive/intrusive_vs_nontrusive.html" rel="nofollow">http://www.boost.org/doc/libs/1_35_0/doc/html/intrusive/intr...</a>
评论 #4500045 未加载
评论 #4499365 未加载
评论 #4500155 未加载
评论 #4500362 未加载
评论 #4500032 未加载
fusiongyro超过 12 年前
I'm not a game programmer and I seldom use C or C++, but I don't find the article particularly convincing. If the motivation is to reduce bugs caused by additional allocations, he wouldn't be avoiding boost or suggesting a copy-and-paste job with his off-the-cuff locking regime. If the motivation is really performance, it seems like one should consider other data structures such as std::vector. Part of the reason to use std::list et. al. is to benefit from the STL functions—hand-writing remove, find, sort, etc. is additional code which will need to be made correct and performant and maintained internally.<p>I understand game programming is a very different enterprise with very different tradeoffs and motivations, but I don't feel well-sold for "pedestrian" application development.
ggchappell超过 12 年前
This points out a real problem, but It think it seems a bit confused about what the problem actually is.<p>In particular, this isn't something "wrong" with std::list. He has a situation where he wants an object to manage its own membership in a mutable container. He says you can't do this efficiently with a simple non-intrusive linked list. He is right. You also can't do it efficiently with an array (std::vector, in this context).<p>You <i>can</i> do it efficiently with an intrusive linked list, as he points out. You can also use a non-intrusive linked list in which each object holds an iterator to itself. Or you can use an associative structure (std::map, std::unordered_map), in which each object holds its own key.<p>The instrusive linked list solution is going to have the fastest container insert &#38; delete operations of all of these. But that doesn't mean it is the best solution for every circumstance.<p>Another point to be made, which he kinda-sorta gets at, is that it is a good idea to know how to code a linked list. The bulk of data structure decisions are just figuring out what already written package to use. But there is definitely still a place for a custom, application-specific linked list, and these are not difficult to write.
评论 #4504104 未加载
xtdx超过 12 年前
One thing about intrusive lists, you have to know and specify every list the item may be on. Maybe you like that, maybe you don't.<p>Also, it doesn't appear the provided code gracefully handles removing an item from a list twice.
评论 #4498558 未加载
评论 #4498541 未加载
ericbb超过 12 年前
See also: <a href="http://lwn.net/Articles/336255/" rel="nofollow">http://lwn.net/Articles/336255/</a><p>(A discussion of Linux data structures, including lists).
ioquatix超过 12 年前
While valid and useful in specific cases, I think that this approach is short-sighted in general. In-place algorithms can lead to significant problems as it is typically hard to enforce strong invariants during the game update loop. In many cases, you wouldn't be erasing elements except as a final step in your game update loop anyway, and you can normally do this as part of a loop where you'd have access to the non-intrusive iterator which can then be removed O(1). I see little benefit to using intrusive linked-lists in this context.
btmorex超过 12 年前
I think there is a subtle bug in his second two person::~person examples. Specifically, from the perspective of other threads an object is no longer valid once its destructor has been called. So, imagine two person objects side-by-side in a linked list. If they are both deleted simultaneously and both destructors get called at the same time, they can no longer safely unlink from each other even with locking because they are technically no longer valid.<p>The first two examples don't have this problem though.
jheriko超过 12 年前
'best defence, no be there'<p>linked lists are seldom the right answer, contiguous blocks of memory are cache - and therefore algorithm - friendly.<p>the stl performance is usually quite easy to beat in special cases as well (i.e. all game code). some stls are terrible as well - the ms one is riddled with locks and all sorts of sledgehammer thread safety measures, which you just don't need if you know which bits of code are threaded and which arent.
评论 #4500109 未加载
cpeterso超过 12 年前
EA open-sourced their EASTL game-optimized container library back in 2007, including intrusive lists. Here is a detailed introduction:<p><a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html" rel="nofollow">http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n227...</a><p>And a github repository that is still maintained:<p><a href="https://github.com/paulhodge/EASTL" rel="nofollow">https://github.com/paulhodge/EASTL</a>
Luyt超过 12 年前
<i>Reliability is more important than speed, and if you’re reduced to using those hacks for speed-gains your program needs help. Remember Y2K bugs!</i><p>I think the reason for dropping centuries from dates was not to gain speed, but to save two bytes. In the 70's of previous millennium, two bytes of storage would cost a lot more than today, and also space on punch cards was limited.