Hard Light Productions Forums
Modding, Mission Design, and Coding => FS2 Open Coding - The Source Code Project (SCP) => Topic started by: Swifty on April 05, 2015, 12:15:10 am
-
While investigating a bug involving BX caches in the prelude to Wings of Dawn's release, I decided to take a stab at the BX file generation code in case I accidentally did something to irrversibly change the format. Fearing the possibility of everyone having to rebuild their BX caches, I wanted to make it less painful and looked into optimizing it. Here is the fruit of my Saturday labor:
Index: code/graphics/2d.cpp
===================================================================
--- code/graphics/2d.cpp (revision 11296)
+++ code/graphics/2d.cpp (working copy)
@@ -32,9 +32,8 @@
#include "gamesequence/gamesequence.h" //WMC - for scripting hooks in gr_flip()
#include "io/keycontrol.h" // m!m
#include "debugconsole/console.h"
-#include "debugconsole/console.h"
+#include "io/timer.h"
-
#if defined(SCP_UNIX) && !defined(__APPLE__)
#if ( SDL_VERSION_ATLEAST(1, 2, 7) )
#include "SDL_cpuinfo.h"
@@ -1454,6 +1453,20 @@
return idx;
}
+int poly_list::find_first_vertex_fast(int idx)
+{
+ uint* first_idx = std::lower_bound(sorted_indices, sorted_indices + n_verts, idx, finder(this, NULL, NULL));
+
+ if ( first_idx == sorted_indices + n_verts ) {
+ // if this happens then idx was never in the index list to begin with which is not good
+ mprintf(("Sorted index list missing index %d!", idx));
+ Int3();
+ return idx;
+ }
+
+ return *first_idx;
+}
+
/**
* Given a list (plist) find the index within the indexed list that the vert at position idx within list is at
*/
@@ -1479,7 +1492,18 @@
return -1;
}
+int poly_list::find_index_fast(poly_list *plist, int idx)
+{
+ // searching for an out of bounds index using the finder means we're trying to find the vert and norm we're passing into the finder instance
+ uint* first_idx = std::lower_bound(sorted_indices, sorted_indices + n_verts, n_verts, finder(this, &plist->vert[idx], &plist->norm[idx]));
+ if (first_idx == sorted_indices + n_verts) {
+ return -1;
+ }
+
+ return *first_idx;
+}
+
void poly_list::allocate(int _verts)
{
if (_verts <= currently_allocated)
@@ -1500,6 +1524,11 @@
tsb = NULL;
}
+ if ( sorted_indices != NULL ) {
+ vm_free(sorted_indices);
+ sorted_indices = NULL;
+ }
+
if (_verts) {
vert = (vertex*)vm_malloc(sizeof(vertex) * _verts);
norm = (vec3d*)vm_malloc(sizeof(vec3d) * _verts);
@@ -1507,6 +1536,8 @@
if (Cmdline_normal) {
tsb = (tsb_t*)vm_malloc(sizeof(tsb_t) * _verts);
}
+
+ sorted_indices = (uint*)vm_malloc(sizeof(uint) * _verts);
}
n_verts = 0;
@@ -1529,6 +1560,11 @@
vm_free(tsb);
tsb = NULL;
}
+
+ if (sorted_indices != NULL) {
+ vm_free(sorted_indices);
+ sorted_indices = NULL;
+ }
}
void poly_list::calculate_tangent()
@@ -1626,6 +1662,9 @@
int j, z = 0;
ubyte *nverts_good = NULL;
+ uint t0, t1;
+ t0 = timer_get_milliseconds();
+
// calculate tangent space data (must be done early)
calculate_tangent();
@@ -1640,8 +1679,10 @@
vertex_list.reserve(n_verts);
+ generate_sorted_index_list();
+
for (j = 0; j < n_verts; j++) {
- if (find_first_vertex(j) == j) {
+ if (find_first_vertex_fast(j) == j) {
nverts++;
nverts_good[j] = 1;
vertex_list.push_back(j);
@@ -1648,6 +1689,10 @@
}
}
+ t1 = timer_get_milliseconds();
+
+ mprintf(("Index Buffer created in %d milliseconds\n", t1-t0));
+
// if there is nothig to change then bail
if (n_verts == nverts) {
if (nverts_good != NULL) {
@@ -1682,6 +1727,8 @@
vm_free(nverts_good);
}
+ buffer_list_internal.generate_sorted_index_list();
+
(*this) = buffer_list_internal;
}
@@ -1696,11 +1743,94 @@
memcpy(tsb, other_list.tsb, sizeof(tsb_t) * other_list.n_verts);
}
+ memcpy(sorted_indices, other_list.sorted_indices, sizeof(uint) * other_list.n_verts);
+
n_verts = other_list.n_verts;
return *this;
}
+void poly_list::generate_sorted_index_list()
+{
+ for ( uint j = 0; j < n_verts; ++j) {
+ sorted_indices[j] = j;
+ }
+
+ std::sort(sorted_indices, sorted_indices + n_verts, finder(this));
+}
+
+bool poly_list::finder::operator()(const uint a, const uint b)
+{
+ vertex *vert_a;
+ vertex *vert_b;
+ vec3d *norm_a;
+ vec3d *norm_b;
+
+ Assert(search_list != NULL);
+
+ if ( a == search_list->n_verts ) {
+ Assert(vert_to_find != NULL);
+ Assert(norm_to_find != NULL);
+ Assert(a != b);
+
+ vert_a = vert_to_find;
+ norm_a = norm_to_find;
+ } else {
+ vert_a = &search_list->vert[a];
+ norm_a = &search_list->norm[a];
+ }
+
+ if ( b == search_list->n_verts ) {
+ Assert(vert_to_find != NULL);
+ Assert(norm_to_find != NULL);
+ Assert(a != b);
+
+ vert_b = vert_to_find;
+ norm_b = norm_to_find;
+ } else {
+ vert_b = &search_list->vert[b];
+ norm_b = &search_list->norm[b];
+ }
+
+ if (norm_a->xyz.x != norm_b->xyz.x) {
+ return norm_a->xyz.x < norm_b->xyz.x;
+ }
+
+ if (norm_a->xyz.y != norm_b->xyz.y) {
+ return norm_a->xyz.y < norm_b->xyz.y;
+ }
+
+ if (norm_a->xyz.z != norm_b->xyz.z) {
+ return norm_a->xyz.z < norm_b->xyz.z;
+ }
+
+ if (vert_a->world.xyz.x != vert_b->world.xyz.x) {
+ return vert_a->world.xyz.x < vert_b->world.xyz.x;
+ }
+
+ if (vert_a->world.xyz.y != vert_b->world.xyz.y) {
+ return vert_a->world.xyz.y < vert_b->world.xyz.y;
+ }
+
+ if (vert_a->world.xyz.z != vert_b->world.xyz.z) {
+ return vert_a->world.xyz.z < vert_b->world.xyz.z;
+ }
+
+ if (vert_a->texture_position.u != vert_b->texture_position.u) {
+ return vert_a->texture_position.u < vert_b->texture_position.u;
+ }
+
+ if ( vert_a->texture_position.v != vert_b->texture_position.v ) {
+ return vert_a->texture_position.v < vert_b->texture_position.v;
+ }
+
+ if ( !compare_indices ) {
+ return vert_a->texture_position.v < vert_b->texture_position.v;
+ } else {
+ return a < b;
+ }
+}
+
void gr_shield_icon(coord2d coords[6], int resize_mode)
{
if (gr_screen.mode == GR_STUB) {
Index: code/graphics/2d.h
===================================================================
--- code/graphics/2d.h (revision 11296)
+++ code/graphics/2d.h (working copy)
@@ -100,10 +100,23 @@
* This should be basicly just like it is in the VB
* a list of triangles and their associated normals
*/
-class poly_list
-{
+class poly_list {
+ // helper function struct that let's us sort the indices.
+ // an instance is fed into std::sort and std::lower_bound.
+ // overloaded operator() is used for the comparison function.
+ struct finder {
+ poly_list* search_list;
+ bool compare_indices;
+ vertex* vert_to_find;
+ vec3d* norm_to_find;
+
+ finder(poly_list* _search_list): search_list(_search_list), vert_to_find(NULL), norm_to_find(NULL), compare_indices(true) {}
+ finder(poly_list* _search_list, vertex* _vert, vec3d* _norm): search_list(_search_list), vert_to_find(_vert), norm_to_find(_norm), compare_indices(false) {}
+
+ bool operator()(const uint a, const uint b);
+ };
public:
- poly_list(): n_verts(0), vert(NULL), norm(NULL), tsb(NULL), currently_allocated(0) {}
+ poly_list(): n_verts(0), vert(NULL), norm(NULL), tsb(NULL), currently_allocated(0), sorted_indices(NULL) {}
~poly_list();
poly_list& operator = (poly_list&);
@@ -115,11 +128,15 @@
vec3d *norm;
tsb_t *tsb;
+ uint *sorted_indices;
+
int find_index(poly_list *plist, int idx);
-
+ int find_index_fast(poly_list *plist, int idx);
private:
int currently_allocated;
int find_first_vertex(int idx);
+ int find_first_vertex_fast(int idx);
+ void generate_sorted_index_list();
};
Index: code/model/modelinterp.cpp
===================================================================
--- code/model/modelinterp.cpp (revision 11296)
+++ code/model/modelinterp.cpp (working copy)
@@ -4381,7 +4381,7 @@
new_buffer.assign(j, first_index);
} else {
- first_index = model_list->find_index(&polygon_list[i], j);
+ first_index = model_list->find_index_fast(&polygon_list[i], j);
Assert(first_index != -1);
new_buffer.assign(j, first_index);
Speeds up creation of BX files by a crazy amount. I tried it on the Diaspora Sobek Battlestar which is about a 100 Meg POF file. Takes about 10 seconds in a Release configuration which is pretty damn good; it takes 6 seconds to load the model with the BX file. In Debug, the Sobek takes about 30 seconds to load with a BX file. Loading it without the BX file with this patch only took 40 seconds.
How did i do it? I used std::sort and std::lower_bound with a custom comparison function. Generating index buffers is currently done brute force but this patch is a lot smarter about finding common verts when building an index buffer. I first sort the verts spatially while keeping track of their indices and then I use a lower_bound to perform a binary search.
Try it yourself. Make a build with this patch, delete a BX file in your cache folder and view the model in the tech room or lab. Heck, maybe with this we can get rid of BX files altogether.
-
10 versus 6 seconds still sounds significant, there will be more models like that as time goes on. I'd say, let's not ditch the cache system just yet. But I really love this feature, should speed up loading by a tremendous amount. Can't wait to see it implemented. :)
-
Yeah, this actually looks like it would make .bx files unnecessary.
-
Yeah, this actually looks like it would make .bx files unnecessary.
When looking at one ship, perhaps.. but a 15-35% increase for all ships across the board when loading missions would be a problem. (Am I understanding bx correctly, that it uses those to speed up mission load times?)
-
Not exactly. This only increases load times the first time a given model is loaded; I'm pretty sure that overall load times for a given mission would not be increased significantly.
-
Hmm OK. Well I'd love to not have to deal with bx files anymore. But a generic increase in model load times (arguably the most important asset that keeps getting more complex in modding) of 15-35% has to go somewhere.
I guess all I'm saying is that removing a feature that is mostly just annoying but would increase load times by that amount just raises a little red flag for me. But I trust you guys.
-
The thing is, this slowdown is only noticeable for really big models, like the Sobek. I'm willing to bet that most campaigns will not feature these beasts in every single mission (and even then, the slowdown should only apply the first time that model is loaded).
-
Well, a Diaspora campaign could as well use a Sobek in every mission. The player being based on the thing would probably require its presence. Also, as times goes on, models in general become more and more detailed. Some day we might have missions with multiple Sobek-level ship classes flying around. As I said, I wouldn't throw BX files out just yet. They do decrease loading times, which are good to keep as low as possible. However, this would certainly mean that bundling those files with mods would not be important anymore.
-
As E said, models don't get unloaded between missions. Once it's resident, it's there forever until the player closes the game.
-
That still means one slow load per game startup, not "one in a lifetime" slow load. Especially testing may be affected, because the usual workflow (at least for me) was "test-quit-adjust-test again", meaning I'll quit the game a lot. I'm not sure how many missions people play in one sitting on average, but it seems to me that the gain from having BX files is significant for it to matter in at least some cases.
-
Yeah, I'm with Dragon on this one. Keeping startup times low is more important than saving a bit of disk space.
-
I think you guys are severely overestimating the amount of time lost here. Seriously, you're basing this on data from one of the largest models ever made for FSO; for normal models, the differences in load times are not really noticeable.
-
I'm open to seeing more representative data, but keeping load times low is pretty important and I'm not really seeing how this benefits the majority of users.
-
*whistles quietly since the collision detection optimizations I did 3 years back increased load times by about 20% and no one ever complained*
Watch, we're going to sneak this update in as well and delete all BX files and you guys won't ever notice. :P
-
Would that be possible to make a launcher flag for this? If that doesn't work (or is too much effort), the best idea would be to compile a test build and stress-test the system on a particularly poly-heavy mod. Again, keep in mind rising model polycounts in FS mods (just look at the recent FSU models and at what looked like a perfectly good HTL model before).
Also, nobody complained before, because at the cost of loading times we got a significant boost to in-game performance. Here, we decrease loading times without any additional drawbacks. The question is whether to go all-out in that regard or save some HD space at the cost of slightly lesser loading time reduction. Ultimately, I think that HD space is cheap enough to be less of a concern than minimizing loading times. But it's not like the other option wouldn't still be a great improvement over what we have now.
-
Here's some quick, non-scientific testing. Loading Artemis with .bx files on debug takes 3 minutes, 13 seconds. Without, 3 Minutes, 12 seconds.
In release builds, loading with .bx files took 36 seconds. Without, 22 seconds.
Yeah. I am not going to think of this as a significant slowdown.
-
Ha ha, oh ****. So it's even faster without the BX files! I guess that would make sense if you think about it, reading from disk is never going to be as fast as reading from cache or memory. And index buffer generation has a disk writing cost too so if we didn't have to write BX files, loading might be even faster...
-
In release builds, loading with .bx files took 36 seconds. Without, 22 seconds.
:eek2: ...Wow.
-
Would that be possible to make a launcher flag for this? If that doesn't work (or is too much effort), the best idea would be to compile a test build and stress-test the system on a particularly poly-heavy mod. Again, keep in mind rising model polycounts in FS mods (just look at the recent FSU models and at what looked like a perfectly good HTL model before).
Also, nobody complained before, because at the cost of loading times we got a significant boost to in-game performance. Here, we decrease loading times without any additional drawbacks. The question is whether to go all-out in that regard or save some HD space at the cost of slightly lesser loading time reduction. Ultimately, I think that HD space is cheap enough to be less of a concern than minimizing loading times. But it's not like the other option wouldn't still be a great improvement over what we have now.
Oh come on... A launcher flag for this? Please. All I said was, hey this raises a red flag, let's take a closer look (aka, I trust scp). If there's anything FSO does not need, it's more launcher flags for stupid reasons.
-
*whistles quietly since the collision detection optimizations I did 3 years back increased load times by about 20% and no one ever complained*
I noticed that load times had gotten longer in general but didn't know what had caused it. Now I know to blame you. :p
-
Also, it's not just a matter of disk space, but maintaining bx files themselves has always been kind of a pain from a mod management standpoint, etc.
-
Also, it's not just a matter of disk space, but maintaining bx files themselves has always been kind of a pain from a mod management standpoint, etc.
Indeed it has... Nothing is more annoying than releasing something only to realize you forgot to include the bx for that last minute update to a complex pof...
-
I remember writing the code that generated those index buffers(don't think I wrote them to file), I remember thinking to myself "this is a ****ty solution, I'll come back to it when it becomes a problem". is this new solution to do a binary search or something? it really should probably be using a hash map (http://www.cplusplus.com/reference/unordered_map/unordered_map/)
-
I finally got around to doing a test of this (using -noibx so I didn't have to perform surgery on the MediaVPs' VP files) and found that loading the Arcadia in the F3 lab in a release build takes my system ~22 seconds without this patch, and ~2 seconds with. This is also how much time it took when I removed -noibx, so (anecdotally-speaking) it would seem that cache files may have just become irrelevant.
-
Well, looks like this is definitely going into trunk as soon as possible. Followed by a dismantling of cache file reading/writing in the model loading code.
-
Anybody got an old system to try this on (Goober)? Curious if the affects are the same on different hardware...
-
I'm happy to test this out, but you caught me in the middle of a move. All of my stuff, including my computer hardware, is piled in the center of the room while the walls get painted. :) I'm currently restricted to just my laptop.
-
Here's some more stats with a slightly old CPU running Linux; the new code is awesome at cutting down the .bx file generation times! Using .bx files still seems to provide a small advantage in most situations on my PC.
(http://i.imgur.com/DVUwsWV.png)
(Note that times are rounded to the nearest second due to the inherent inaccuracy in my use of a stopwatch for timing)
(Also note that I made a few trivial changes to the patch to let it compile with gcc, and remove some warnings in 2d.h that were being spewed everywhere)
-
Well, looks like this is definitely going into trunk as soon as possible. Followed by a dismantling of cache file reading/writing in the model loading code.
I'd say a difference in loading times from 10 seconds to 8 seconds is enough to be worth leaving .bx files in the engine (and if some systems get better performance from not reading off the drive, they can always use -noibx).
-
In the above chart, the difference was only two seconds though. I do not think that's significant, or even particukarky noticeable.
-
The difference is more pronounced on debug (and when debugging a mod, you would spend quite some time running that), not to mention that between 8 and 10 seconds, it's still a 20% difference. I'd imagine that more complex models would make this noticeable. Since the flag to disable cache files is there, I'd say, the code should be left in. Mods will be free to discontinue distributing .bx files if they want, and users can just disable their generation if they're short on HD space.
-
Just out of curiosity, is the difference on debug builds perhaps due to just the extra code solely relating to debugging? Logging, etc? If so, it doesn't really mean the algorithm is much faster, just that we've bogged down the old path.
-
4 seconds lost on debug. 2 seconds lost on release. On one of the most complex missions. No, dragon. There really is no good reason why we should keep cache files around.
-
Or reverse the existing noibx flag to ibx which enables the feature rather than disabling it. That way people have the option to enable it, rather than it defaulting to enabled. You could even hide it under troubleshooting.
-
4 seconds lost on debug. 2 seconds lost on release. On one of the most complex missions. No, dragon. There really is no good reason why we should keep cache files around.
Look at it another way. Leaving the cache in increases the performance by 20%-24%. Enough to keep them, IMO, regardless of how the absolute figures. How long do you expect Icarus to remain the most complex mission around? In the future, somebody is almost certainly going to come and top it (maybe even BP itself). Thinking in absolute values is much less future-proof than percentages.
-
Time doesn't increase if missions get more complex. It only increases as a function of number of vertices in a model. The time function is logarthmic so a crap load of small models is really no problem compared to one really large model like the Theseus. Most models are expected to be well optimized anyway, most of them should be staying under 65,000 verts in order to keep the index buffers small and fast for the post-transform cache on the GPU. If you need to go over 65,000, there should only be at most like four models like that in a mission or else you're going to suffer in-game performance problems.
So no, average case, the load times will stay the same or be even faster. If your load time is slightly longer by a few seconds, well, you already have bigger problems on your hand in-game.
-
There's a point you're missing, Dragon, which I brought up earlier in my testing: This load time increase is extremely variable. It depends a lot on how fast your HDD is. On slow drives, the time needed to load buffer files from disc is longer than the time needed to generate those same buffers from scratch.
This is why I keep arguing for a removal of buffer files: In absolute terms, we're talking about a couple seconds of loss at maximum. That's barely noticeable; if we had slipped this in without telling you about it, you wouldn't have noticed. You are, in my opinion, making a lot of noise over nothing.
Regarding mission complexity, here's another quick test performed on my system. BP massive battle, using a bunch of rather large models. With cache, it takes 33 seconds to load. Without, 27 seconds. In other words, in a situation where I would load the same mission repeatedly, a combination of read caching by the OS and the speedup here makes the whole thing faster without the cache files.
Please, run your own tests. Make your own experiments. But do NOT talk to me about how big a deal 2 seconds are.
-
Yup, I should note that in my tests I have FSO on a SSD, Diaspora on a 7200rpm SAS HDD, and Linux caches anything on the filesystem into spare RAM after its 1st read (Windows probably does this as well? But I haven't tested/confirmed it). Or in other words, my tests had removed nearly all influence of disk access on the results.
e.g. 1st FSO start after flushing disk cache: ~15 secs; start FSO with disk cache intact, ~10 secs, restart mission without restarting FSO, ~7 secs (IOW disk access times are a bigger factor than the patches changes)
-
Yup, I should note that in my tests I have FSO on a SSD, Diaspora on a 7200rpm SAS HDD, and Linux caches anything on the filesystem into spare RAM after its 1st read (Windows probably does this as well? But I haven't tested/confirmed it). Or in other words, my tests had removed nearly all influence of disk access on the results.
It's possible my system was doing this as well; I had a longer load on my first read with the cache files than I did on subsequent reads with the cache files; I dismissed it at first as unreproducible behavior, but in hindsight, the OS was probably caching the cache files, causing identical (or near-identical) performance with the -noibx version with the patch.
In that case, the performance increase on my HDD under NTFS is severely in favour of getting rid of cache files; ~45 seconds versus ~19 seconds loading Icarus, and ~5.5 seconds versus ~2 seconds loading the Arcadia through the F3 lab.
-
This load time increase is extremely variable. It depends a lot on how fast your HDD is. On slow drives, the time needed to load buffer files from disc is longer than the time needed to generate those same buffers from scratch.
I think that this is actually a good argument for keeping the cache and using the -noibx flag to remove it. That way, the user will be able to optimize performance himself. If you throw out the system, it will increase for some and drop for others. We already have a way of disabling cache files, I don't think this needs to be messed with.
-
You seem to be under the mistaken impression that this is a discussion. The decision has been made; you'll just have to wait a few seconds for missions to load (or, who knows, you might as well get faster load times).
-
Oh for god's sake, all he's asking for at this stage is the option.
-
I also firmly believe that the mistake here was to let us know there would be a disadvantage by not using the cache files. As an architect, I'm intuitively fully behind any attempt at getting rid of any redundacies which are only a source of potential further issues and bugs in the future, with no genuine advantages at all. No, 2 seconds less is not worth it. Simpler the code is, the better it is to take care of it, and the faster old things like cache files can be deprecated. Swifty's trick is awesome and should be celebrated! :yes:
-
Oh for god's sake, all he's asking for at this stage is the option.
Yes, and I am of the opinion that if we can make the code simpler and reduce the number of commandline options we have (and we have a ton; it's pretty ridiculous) without any adverse effects, we should do so.
-
When are we going to get a pull request for this? I miss the shorter load times. :nervous:
-
Yes, and I am of the opinion that if we can make the code simpler and reduce the number of commandline options we have (and we have a ton; it's pretty ridiculous) without any adverse effects, we should do so.
What exactly is the problem with commandline options anyway? It's what makes FSO customizable, and they're easily accessible via launcher. I don't understand the recent phobia against them. Commandline options are something that would normally go into in-game options menu, with the added bonus of being editable outside of game. We can't exactly mess with FSO's in-game options (being limited by the interface art), so that's the best we can do. What is ridiculous is, IMO, the drive to move away from a perfectly good, fairly transparent customization system. Flags that set lighting values could be handled better, but I think that the way to do it would be to modify the launcher, not moving those flags to a table where the user can't usually access them.[/rant]
For the end user, more customizability=better. They say you can't please everyone, but in some cases, you can, if you give them enough customization choices. Unless we can add another tab into the in-game options menu, commandline options are the best way to do so.
-
Commandline options have their place. When they can be used to customize the experience, or make major changes to the amount of ressources the engine needs.
If the removal of cache files had a big impact one way or another, this would not be a discussion. But it doesn't. It's at worst neutral. As such, having an option that will have almost no effect for end users makes no sense. It just introduces additional ways in which things can go wrong, additional behaviours that have to be accommodated. Those are the kinds of options that should be cut.
Customizability is great. But only when it actually means something.
-
Maybe some stuff that can be applied to retail would be unavailable, but that doesn't actually break anything.
So you think that people using retail assets shouldn't be allowed to, say, enable 3D radar? Or framebuffer shockwaves? That people with retail assets shouldn't be allowed to enable the rearm/repair completion timer?
-
The discussion about commandline options and ingame UI to set/manipulate them has been moved here: http://www.hard-light.net/forums/index.php?topic=89675.0