Array wrapper that uses uint16 array to store individual bits.
Has two extra methods useful for TileClass: https://code.wildfiregames.com/D1631
Differential D1637
BoolArray array wrapper. nani on Sep 22 2018, 2:06 AM. Authored by
Details Array wrapper that uses uint16 array to store individual bits. Has two extra methods useful for TileClass: https://code.wildfiregames.com/D1631 Use in Tileclass.js
Diff Detail
Event TimelineComment Actions Does our spidermonkey support Uint8Array/Uint32Array? It'd be good to compare them by performance/memory usage.
Comment Actions Why not move this to globalscript/? There could be use cases outside rmgen (triggerscripts comes to mind) Comment Actions I checked the map gen times for 8 ,16 ,32 in multiple maps and haven't found any notable difference. Haven't checked the memory usage. Comment Actions While that might be true the methods isSomeNotZero and isSomeNotOne used in in TileClass.js do improve map generation time (tested 20% improvement average if i remember correctly). Comment Actions Sure I'm not saying this is is useless :) Comment Actions If the feature proposal is accepted, it should be moved over there. Sure, but the problem is that you would have to go through the JS Interface for every read or write access if we use that.
We need a dedicated test to check the performance gain. The trade-off between the advantages and disadvantages of code complexity and performance must be sufficient.
Comment Actions On the importance of the feature: The maximum mapsize that random map scripts can currently create is 512. It would be desirable if we could use higher-resoluted grids to store TileClasses. So it seems we have to replace the current code with code that is both faster and less memory consuming. So I don't know if this is the case for this patch. On the importance of having exactly one patch per feature:
Unique feature 1 is the boolarray in D1637, Since the code here is an intentional performance improvement and might allow for a gamechanging memory impact, The measurement that I recall being taken was testing every of your diffs against none of your diffs. Merge conflicts are expected (both features having to change the same line), but that doesn't invalidate the importance of being able to judge the validity of each of each feature separately. The performance and memory cost of the BoolArray wrapper could be negative, then the patch (but not the 27 thing) should be dismissed, So we should not only determine this patch to be a step, but also the direction of the step. Can either measure, or try to argue from the memory use of the implementation. On the importance of considering all alternatives: We need to imagine, construct, determine, make up any possibility that would allow us a performance benefit of two orders of magnitude (100x speed hack) to achieve LordGood grade random maps using higher resoluted tileclass grids. @vladislavbelov How can we implement a 2D bool array (rasterization of an an arbitrary area) with the best performance and memory-footprint? We need it to be 100x faster and use 16x less memory!! C++ or JS as possible Comment Actions Since I was mentioned here and all of this has been discussed with the author before.
Comment Actions Thanks for the requested response (I only recalled you spoke about doing something with C++, but not which aspect would be moved.)
Which iteration do you mean specifically? Currently TileClass comes with
This revision proposal uses an array of an u16-array, the previous code with RangeOp removed also uses only an array of an u16 array?
Reverting the commit is an action, but first we need to establish that this is correct and the best choice among alternatives. First the reasons, then the actions. We discussed all of this few months before, but the reasons should be in this document. The question is whether rangeOp could provide value, or whether it was a too hypothetical idea that covers truly no use case. There are different aspects, the 27 condition, the rangeOp, and the ability to add a tileclass multiple times per square. I need to run the code again, it's not so easy to tell from a webbrowser, but I see the tool of reverting something being likely indeed.
There is a mismatch between the < 27 and >= 27 code path, creating different maps, nani had investigated it too. It would be good to know which one of the two is wrong in order to fix it if it's the one we keep. IIRC One of the two algorithms included the last item of every line of an area, the other one excluded it.
So the question is
If C++ is truly better, then this patch may be a significant improvement that would still be wrong. Comment Actions
I guess you would be out of the loop on this one. But the 27 mismatch was found. And I failed to find any mismatches. But nani claimed that he found mismatches in water maps (only). (This was independent work from both sides, so it is hard to establish conclusions). Comment Actions
Back then, I started implementing it in a way which does not expose any tile class to js. Engine.AddTileClass(ID, size); Engine.AddToTileClass(ID, [p, q, r]); Engine.TileClassGetPointsInRadius(ID, p, radius); And a C++ Tileclass which gets added to a map or something accessed via ID. Comment Actions It depends on how one tests, if one tests on a map where all distances are smaller than 27, then it obviously creates the same results as the code where the <= 27 condition is replaced with true.
Terribly bad, terribly good, or anything in between. We will find out sooner or later if we want 0 A.D. maps to reach the next level. Yay future! or something Comment Actions Well yes. The current TileClass.js uses wrong values for the rangeOP. The way I tested it, there would have been no false results like that. That was how the error was found, so I guess the methodology is correct. Comment Actions This diff does two things: reduce the size of the memory allocated needed for the array and exploit the 16 bit type values to to check the binary information of upto 16 tiles in one go. Comment Actions
How much of a gain do you think it needs to achieve to make it worth sacrificing the JS-pureness? (answer expected as a number, 100%, 200%?) Comment Actions
The factor 3-4x is still misleading nani (see post above). 100% is a lot, if a map generation time can be reduced from 30s to 15s with that, that would put the threshold for an argument not to use that quite high up. Comment Actions The tileclass optimization patch is using this patch only. So, the performance improvement is a direct result of using this. Or we can always write a new data structure that can eliminate half the remaining grid on each iteration. Comment Actions
As for memory consumption:
Comment Actions A giant mainland map doesn’t really prove it. A large grid with a few points is what mainland offers and is exactly what the bool array method excels at. I wonder how it would perform in a grid where it would have to go to the bit-by-bit check quite frequently. Comment Actions "svn + booArray + tileClass patch" sounds a lot like measuring multiple patches at a time, and I'm not sure what "tileClass patch" refers to, in particular whether it includes the 27 diff and other logic changes. We should have one patch per feature and measure one feature at a time. Comment Actions Tileclass patch refers to actually using this thing. And there are a few cleanups in there like nuking rangeOP. But the whole performance improvement is the direct result of solely using this. Comment Actions (I assume you have checked the other sizes. There is a tradeoff between faster iteration and the number of false negatives.) Comment Actions
Somewhere between 30% (most cases) to 50% faster. Comment Actions
Thanks for testing it, sounds promising. I will try too once I open my IDE again and closed some hundred revision proposals...
Ambush is an animal. Canyon too. Comment Actions
(Branches are useful if you have multiple patches that depend on each other, so you can rearrage the commits and pop one of them at a time into the review queue. If it's a standalone patch that doesn't have merge conflicts with others, you can create a revision proposal or paste and then there is one backup of it. Also I used a messy directory per year/month/day for 0ad notes, abandoned patches etc.) Comment Actions (Maybe add an iterator?, for something like tileclasses, it may not be relevant, but I assumed this was not to be restricted rmgen/ ) Comment Actions Can't really speak on hypotheticals. But less really speaking on it: Bool-arrays would be generic, so they might have a use case for iterators, but what would be the use case for TileClasses outside of rmgen/? Also depends on how the interface would look like, since the class would mostly be accessed by JS, not C++, unless you're planning for C++ rmgen support, which maybe thinkable, but sounds a bit hardcore (as the map would have to be compiled into the binary or into a separate binary, or shared library). I would guess JS has legitimate reason to iterate over a tileclass grid, but dunno if that would be faster to accomplish via next() prev() JS functions rather than accessing the N'th position? Mostly we need to know whether TileClasses must follow JS or C++ (comparing the most performant JS with the most performant C++). I have reason to take some measurements, which I can accomplish as soon as I finished my stuff journey, run this application again and fixed defects. Otherwise the other participants remain free to use the service to share or produce more information to help decide on the case. Comment Actions 80% improvement on some maps. Already decided. As mentioned before, js “pureness” is a moot point. Take what you can. Comment Actions Overlapping logic is present in the tileclasses currently. If a generic bit array structure is desired, it could be placed into globalscripts and TileClass could be updated to use that for the underlying storage. Also rename BoolArray to BitArray as the latter is more descriptive. |