- Forum
- General C++ Programming
- Filesystem, handling files/records
Filesystem, handling files/records
Pages: 12
Hey. I created a table in mysql with 1000000 records / rows in it. My columns are "id (primary key, auto incr.)" And "quantity".
When I request ALL records, ALL columns from that table ORDER by ASC / DESC on Quantity, it takes 1 second for the request to be completed. But when I do the same on "id", instead of Quantity it takes 0 seconds.
Why is it faster to order by "id" instead of "quantity"?
My second question is:
How can I do something similar without dbms. That is, to load 1000000 records / filenames orders by ASC / DESC as fast as the database did as best (0 seconds)
If I have 1000000 txt files and I FIRST read in all of the filenames for example, and THEN sort/reorder everything with some algorithm/program it will take longer than 1 second... Maybe if I have filenames called after unique id's(1,2,3...), I could save the last file-number somewhere and start reading backwards, that wouldn't waste as much time.(maybe there is a better way of doing this? let me know)
When I request ALL records, ALL columns from that table ORDER by ASC / DESC on Quantity, it takes 1 second for the request to be completed. But when I do the same on "id", instead of Quantity it takes 0 seconds.
Why is it faster to order by "id" instead of "quantity"?
My second question is:
How can I do something similar without dbms. That is, to load 1000000 records / filenames orders by ASC / DESC as fast as the database did as best (0 seconds)
If I have 1000000 txt files and I FIRST read in all of the filenames for example, and THEN sort/reorder everything with some algorithm/program it will take longer than 1 second... Maybe if I have filenames called after unique id's(1,2,3...), I could save the last file-number somewhere and start reading backwards, that wouldn't waste as much time.(maybe there is a better way of doing this? let me know)
| When I request ALL records, ALL columns from that table ORDER by ASC / DESC on Quantity, it takes 1 second for the request to be completed. But when I do the same on "id", instead of Quantity it takes 0 seconds. Why is it faster to order by "id" instead of "quantity"? |
| If I have 1000000 txt files and I FIRST read in all of the filenames for example, and THEN sort/reorder everything with some algorithm/program it will take longer than 1 second... Maybe if I have filenames called after unique id's(1,2,3...), I could save the last file-number somewhere and start reading backwards, that wouldn't waste as much time.(maybe there is a better way of doing this? let me know) |
| How can I do something similar without dbms. That is, to load 1000000 records / filenames orders by ASC / DESC as fast as the database did as best (0 seconds) |
Hey Helios. Thanks for your reply. You mention OS on disc data. But how does it differ from how dbms does it? They must also get the content from somewhere. Their files are also stored on the hard drive?
The answer is a bit complicated, but basically, finding the physical location of a file on a disk involves traversing a B-tree (or some other tree-like structure), and is slower than finding an offset within a file you've already opened. Particularly in the case of HDDs, since it involves head seeking. The DBMS also stores its indices as B-trees, but it's more eager than the OS to cache them in memory (the OS has to share memory with user applications, while the DBMS can assume that most of the computer's memory will go to DB operations), also it stores its data in a few big files, rather than many tiny files, to reduce time wasted traversing OS data structures.
Allright. Thanks for the tip about index. It does some magic, clearly. It will work for now.
I also wish to get a better understanding of what's happening behind the scenes, and how I can achive the same effect only with c++ some day. Do you have some idea how they structure the columns and rows within the files? Are ALL rows/records from one table all in the same file? And are they using regular textfiles with fancy extensions, or is it some other magic?
I also wish to get a better understanding of what's happening behind the scenes, and how I can achive the same effect only with c++ some day. Do you have some idea how they structure the columns and rows within the files? Are ALL rows/records from one table all in the same file? And are they using regular textfiles with fancy extensions, or is it some other magic?
| And are they using regular textfiles with fancy extensions, or is it some other magic? |
| Do you have some idea how they structure the columns and rows within the files? |
| Are ALL rows/records from one table all in the same file? |
Generally speaking though, the fewer files, the better. It would not surprise me if there's a DBMS out there that allows using a raw partition (without OS format) to take direct control of the data layout on the hardware.
Sounds like surgical precision when it comes to hitting the exact right spot/offset on files containing massive amount of records/rows... And every time something gets removed, inserted and so on. It feel very fragile and insecure :) Feels alot safer making them independent somehow.
You mentioned "without OS".
Is it possible to get deeper under the hood and work from there somehow? At the moment im stuck with what the winapi is providing me. It feels like it keeps people above the surface ;)
Is it possible to get deeper under the hood and work from there somehow? At the moment im stuck with what the winapi is providing me. It feels like it keeps people above the surface ;)
| It feels like it keeps people above the surface ;) |
That might be because under the surface is actually rather complex :+) The API provides an interface to abstract away all the nasty details.
| ...... and how I can achive the same effect only with c++ some day. |
Not wishing to hold you back, but it sounds like trying to reinvent the wheel. But some people do that for a learning experience, for example someone on this forum wrote his own version of std::vector. His (and your) code may not be as good as the real thing but a lot could be learnt, just be prepared for all the complexity and writing a lot code to achieve some thing fairly simple.
| If I have 1000000 txt files and I FIRST read in all of the filenames for example, and THEN sort/reorder everything with some algorithm/program it will take longer than 1 second... Maybe if I have filenames called after unique id's(1,2,3...), I could save the last file-number somewhere and start reading backwards, that wouldn't waste as much time.(maybe there is a better way of doing this? let me know) |
Have you tried doing that with C++, with sorting of std::vector<Record> where Record is a type that holds your data, you might be surprised on how well it does? I am saying do this without the unique ID and reading backwards. The DB would be faster, but you may be surprised at how quick C++ can do it, especially with 1 table. Of course the DB is going to be much better with multiple table queries.
Remember the STL algorithms are as optimized as much as can be, you won't be able to come up with something better, but can choose different STL containers. But the performance varies depending on exactly what operation is being done on what container.
| You mentioned "without OS". Is it possible to get deeper under the hood and work from there somehow? At the moment im stuck with what the winapi is providing me. It feels like it keeps people above the surface ;) |
You can create a partition on the disk and not format it. The system will then let you read/write to that partition as if it was an on-disk array - a giant block of bytes.
On Windows you don't need anything other than the Windows API to do this. CreateFile() can be used to open partitions. You just need to use the special paths "\\\\.\\" (those backslashes are escaped; it's backslash backslash dot backslash). Google "windows api open partition" for examples.
On UNIX partitions are typically represented as files in /dev. For example, /dev/sda1 is usually (but not necessarily) the system partition. You can use normal file open functions, such as fopen() or std::fstream::open().
Notes:
* You will probably need administrator privileges to open partitions for read/write.
* Never write directly to formatted partitions or that are mounted by the OS! It could very easily cause data loss.
TheIdeasMan:
Hey man. I actually prefer "regular" arrays over vectors. It's always faster to read in the same amount of data to the regular array compared to the vector. It's not a massive difference, but it's there on large reads...
helios:
Is it worth going down this road? Im prepered to it if you think I can get even a little speed boost when I'm reading in data.
I inserted 1 000 000 lines in a regular txt-file like this:
John
Anna
Helios
and so on....
On my computer it took 0.40s - 0.55s to read in 1 000 000 rows of data like above with getline().
I also tried a version where I seperated them with "space" instead of a "newline", like this:
John Anna Helios
In this (second) version/example i used ">>" instead of getline(), but it went faster in the first example when I read in all the content using getline(). In the second example here with ">>" it went up to 0.60 - 0.65.
But 0.40s - 0.55s still feels slower than a mysql query for the same thing(a regular query/read in for a table as it already is)
The only way I could improve the time was if I read the entire text-file/rows directly in to one variable, instead of separated indexes, but that's not practical of cource ( not in any way that I know of ).
Any ideas? If mysql can do it that fast, then it should also be possible for me to do it within the same time, because it's all happening on the same machine. What do they know that I dont? ;)
Hey man. I actually prefer "regular" arrays over vectors. It's always faster to read in the same amount of data to the regular array compared to the vector. It's not a massive difference, but it's there on large reads...
helios:
Is it worth going down this road? Im prepered to it if you think I can get even a little speed boost when I'm reading in data.
I inserted 1 000 000 lines in a regular txt-file like this:
John
Anna
Helios
and so on....
On my computer it took 0.40s - 0.55s to read in 1 000 000 rows of data like above with getline().
I also tried a version where I seperated them with "space" instead of a "newline", like this:
John Anna Helios
In this (second) version/example i used ">>" instead of getline(), but it went faster in the first example when I read in all the content using getline(). In the second example here with ">>" it went up to 0.60 - 0.65.
But 0.40s - 0.55s still feels slower than a mysql query for the same thing(a regular query/read in for a table as it already is)
The only way I could improve the time was if I read the entire text-file/rows directly in to one variable, instead of separated indexes, but that's not practical of cource ( not in any way that I know of ).
Any ideas? If mysql can do it that fast, then it should also be possible for me to do it within the same time, because it's all happening on the same machine. What do they know that I dont? ;)
Last edited on
| Is it worth going down this road? |
You'll never approach MySQL using text files. Processing text is just more expensive than processing binary files.
I'll reiterate my suggestion to just use SQLite, but if you really want to do it yourself, you'll have to define a binary format for your data. Keep in mind that things like rows of variable length are generally more expensive to process than rows of fixed length.
1. If I work with binary. Will it be the same result/time in the end? Because I still need to convert them to human readable formats before I print it out.
2. How do I set fixed length, and then process them the right way?
2. How do I set fixed length, and then process them the right way?
1. I don't understand the question.
2. "Set"? No, you don't "set" it. There's no function you can call that will "set" this. You have to design the binary format and your code so that the data will have this property.
2. "Set"? No, you don't "set" it. There's no function you can call that will "set" this. You have to design the binary format and your code so that the data will have this property.
I tried this now.
fstream myfile;
int main () {
myfile.open("test.bin", ios::out | ios::binary | ios::app);
int i = 0;
while(i < 1000000) {
myfile << i << "\n";
i++;
}
}
The time here is not importent. What I want to know is if i'm doing it right? Because after I inserted the testrecords, I expected to see a representation of ones and zeros. But it looks like they are saved as "regular" characters/numbers in the bin file. (1,2,3,4,5,6 and so on) I looked at it with notepad++.
I tried it out anyway. The speed of reading in the rows is importent and I dont se much difference doing it this way instead of the other method explained in my previous comment. (to use plain txt files instead of binary)
This is the code I used to read in everything from the BIN-file:
fstream myfile;
int main () {
string * a;
a = new string[1000000];
myfile.open("test.bin", ios::in | ios::binary);
int i = 0;
while(getline(myfile, a[i++]))
}
Any other suggestions that can improve the speed? Im stuck on 0.40-0.50. As I mentioned, maybe I did it wrong. I have little experience with binary so correct me if needed.
fstream myfile;
int main () {
myfile.open("test.bin", ios::out | ios::binary | ios::app);
int i = 0;
while(i < 1000000) {
myfile << i << "\n";
i++;
}
}
The time here is not importent. What I want to know is if i'm doing it right? Because after I inserted the testrecords, I expected to see a representation of ones and zeros. But it looks like they are saved as "regular" characters/numbers in the bin file. (1,2,3,4,5,6 and so on) I looked at it with notepad++.
I tried it out anyway. The speed of reading in the rows is importent and I dont se much difference doing it this way instead of the other method explained in my previous comment. (to use plain txt files instead of binary)
This is the code I used to read in everything from the BIN-file:
fstream myfile;
int main () {
string * a;
a = new string[1000000];
myfile.open("test.bin", ios::in | ios::binary);
int i = 0;
while(getline(myfile, a[i++]))
}
Any other suggestions that can improve the speed? Im stuck on 0.40-0.50. As I mentioned, maybe I did it wrong. I have little experience with binary so correct me if needed.
Last edited on
No,
You shouldn't even be putting newlines in binary. A newline doesn't mean anything special in binary. It's just a 0x0A (10 in base 10, 00001010 in 8-bit binary).
I suggest reading this article
http://www.cplusplus.com/articles/DzywvCM9/
In short, you're supposed to do something like this
Speed improvements? Well, for one, don't construct a million std::strings, because each of those requires their own separate heap memory, which will ruin your cache. Also make sure optimizations are turned on.
Don't even use strings unless you have to. Certainly don't want to be using getline with binary files.
You want to use read.
operator<<(istream&, T) always outputs readable characters, not binary.You shouldn't even be putting newlines in binary. A newline doesn't mean anything special in binary. It's just a 0x0A (10 in base 10, 00001010 in 8-bit binary).
I suggest reading this article
http://www.cplusplus.com/articles/DzywvCM9/
In short, you're supposed to do something like this
|
|
Speed improvements? Well, for one, don't construct a million std::strings, because each of those requires their own separate heap memory, which will ruin your cache. Also make sure optimizations are turned on.
Don't even use strings unless you have to. Certainly don't want to be using getline with binary files.
You want to use read.
|
|
Last edited on
Ganado. Thanks for the feedback.
Okej, any idea how to read in the records without making an index for every one of them?
Lets imagine a website like fb for example. They get a lot of querys at the same time to the SAME database(lets say names) every second. Do you think their db is prepared in RAM or do they search on disc every time?
| Speed improvements? Well, for one, don't construct a million std::strings, because each of those requires their own separate heap memory, which will ruin your cache. Also make sure optimizations are turned on. |
Okej, any idea how to read in the records without making an index for every one of them?
Lets imagine a website like fb for example. They get a lot of querys at the same time to the SAME database(lets say names) every second. Do you think their db is prepared in RAM or do they search on disc every time?
If every server rack cached the database in their own ram, what would happen if someone changed the value on disk?
The way how a CPU solves this is by giving the other cores a dirty bit so they are forced to go to the disk to get the new value.
But is it really practical for a server rack to communicate to all the other server racks to go and refetch the data on every write? No.
For the other question reading the data into indexes you can use the example http://www.cplusplus.com/reference/istream/basic_istream/tellg/
To get the size of the file, create a vector of ints, resize the vector to, the size of the file divided by sizeof(int) (assert check if the remainder of the size against sizeof(int) is == 0). Then use the read function to the vector using data(), like how Ganado shows.
Also there is nothing wrong with using plain text, it is much more convenient even if it is slow, since from all that we know, your actual use case could be nowhere near 1 million lines.
Also I do not see your benchmarking code, and you have not told us if you are using an SSD or what your compilation flags are, and you should write more rigorous tests with loops since files can have lag spikes from the OS randomly locking it.
The way how a CPU solves this is by giving the other cores a dirty bit so they are forced to go to the disk to get the new value.
But is it really practical for a server rack to communicate to all the other server racks to go and refetch the data on every write? No.
For the other question reading the data into indexes you can use the example http://www.cplusplus.com/reference/istream/basic_istream/tellg/
To get the size of the file, create a vector of ints, resize the vector to, the size of the file divided by sizeof(int) (assert check if the remainder of the size against sizeof(int) is == 0). Then use the read function to the vector using data(), like how Ganado shows.
Also there is nothing wrong with using plain text, it is much more convenient even if it is slow, since from all that we know, your actual use case could be nowhere near 1 million lines.
Also I do not see your benchmarking code, and you have not told us if you are using an SSD or what your compilation flags are, and you should write more rigorous tests with loops since files can have lag spikes from the OS randomly locking it.
| If every server rack cached the database in their own ram, what would happen if someone changed the value on disk? |
The only ways for data to change without the DB knowing it are if the kernel itself does it, if another process writes directly to the underlying device, or if a hardware error corrupts the data. If any of these things happen, yes, the in-memory cache will be out-of-sync with the on-disk data, and the behavior is unpredictable.
Another thing that can go wrong is a memory error (e.g. caused by manufacturing defects or radiation, typically in the form of cosmic rays) altering the contents of active memory. These errors are why ECC memory is so common in server hardware.
| The way how a CPU solves this is by giving the other cores a dirty bit so they are forced to go to the disk to get the new value. |
| But is it really practical for a server rack to communicate to all the other server racks to go and refetch the data on every write? No. |
Pages: 12