Arrays versus Linked Lists

Started by
14 comments, last by Geometrian 13 years, 3 months ago
Hi,
Quote:Another issue is whether you are timing the code correctly, or using too small a dataset such that external factors can sway the measurement significantly. I don't suppose you can show us the source code for these tests, and the actual results you get on your machine?
As I said, it was a loose measurement, taken with breakpoints and counting seconds.

I think I may have found the problem, though. It seems that the allocation itself was fast enough, but the surrounding code that reads through the file is not. My mistake for not catching that straight off.

The code is part of an object loader (which loads a .obj and associated .mtl if there is one) into a set of data for rendering. The C++ code reads the file once to determine how large it need be, the memory is allocated, and then the file is read again to load the data into it. The Python code reads the file once. This may be where the speed difference is.

The C++ sections where the file is read look something like:
string line;ifstream obj_file(filename.c_str());while (!obj_file.eof()) {    getline(obj_file,line);    //Process line, either counting it, or adding its data, depending on    //what it's doing to the file at this time.}
The Python section where the file is read looks something like:
file = open(os.path.join(*filename),"r")for line in file.readlines():    #process line, and add it to the proper list

Because the C++ code is opening the file several times and reading presumably one line at a time, it's going to take longer.

New question: basically, the problem is that the file contains content of an unknown size. What is the fastest way to create a data structure that contains it, in RAM--including the time spent reading from the file?

Thanks,
-G

[size="1"]And a Unix user said rm -rf *.* and all was null and void...|There's no place like 127.0.0.1|The Application "Programmer" has unexpectedly quit. An error of type A.M. has occurred.
[size="2"]

Advertisement
Quote:My hypothesis on this is that finding an open section of RAM large enough is somewhat tricky for the C++ code,

iostream is clumsy and inefficient, especially with getline. There is no good out-of-box alternative.

When it comes to mangling lots of text, Python (or similar languages) run circles around C++, unless C++ code is really optimized (finite state machines for parsing).


Memory issues are not a problem here, in C++ just use std::vector - it is not the bottleneck.

Or better yet, just stick with Python.

Quote:What is the fastest way to create a data structure that contains it, in RAM--including the time spent reading from the file?

In-place architecture-specific representation that is read directly from disk image. But for most purposes, this isn't practical. In practice, this would look something like:
struct Model1 {  int faceIndices[43];  float vertices[385];  float texture[223];}Model1 model;fread(f, &model, sizeof(Model1));
Quote:Or better yet, just stick with Python.
Python is beautiful to use. That's why I wrote the thing in Python to begin with. But, it's now been several years, it's basecode, it's slow, and I'm porting it to make it faster.
Quote:Memory issues are not a problem here, in C++ just use std::vector - it is not the bottleneck.
Yeah. My mistake.

So, fastest way to load a file?

[size="1"]And a Unix user said rm -rf *.* and all was null and void...|There's no place like 127.0.0.1|The Application "Programmer" has unexpectedly quit. An error of type A.M. has occurred.
[size="2"]

Why don't you combine fseek to end, ftell to get total size, allocate memory, fseek to the beginnig to actually read it.

I guess there is something like this in the STL, but I haven't actually used it in ages, as I work with C# and university assignments are in C.

Anyway, fseek should be pretty fast operation, as well as ftell.
Don't use .obj files, they're a pain. I use a custom format that basically resembles the format I need for the GPU with all the information needed for the draw calls, I then mmap the file in and upload the relevant bits to the GPU.

I have about 120 lines of code to import an obj/mtl file, and 14 lines to load my own custom format (4 more lines of code to upload it to the GPU).

So, my suggestion, move the conversion of the model to an offline process, then you don't have to worry about how fast it is.

Regards
elFarto
Quote:So, my suggestion, move the conversion of the model to an offline process, then you don't have to worry about how fast it is.
It's a library, and I want it to be able to load .obj files quickly, even if it will convert them to another faster (binary) format.

My tests showed that fseek, ftell, and fread are plenty fast enough. My code now runs 1346 times faster.

Thanks,
-G

[size="1"]And a Unix user said rm -rf *.* and all was null and void...|There's no place like 127.0.0.1|The Application "Programmer" has unexpectedly quit. An error of type A.M. has occurred.
[size="2"]

This topic is closed to new replies.

Advertisement