Slashdot Mirror
No, It's Not Always Quicker To Do Things In Memory
itwbennett writes: It's a commonly held belief among software developers that avoiding disk access in favor of doing as much work as possible in-memory will results in shorter runtimes. To test this assumption, researchers from the University of Calgary and the University of British Columbia compared the efficiency of alternative ways to create a 1MB string and write it to disk. The results consistently found that doing most of the work in-memory to minimize disk access was significantly slower than just writing out to disk repeatedly (PDF).
This is the dumbest research I've seen in 2015. There was actually no computation involved -- they just wanted to write a long string to disk. They concluded that adding the superfluous step of concatenating strings in memory, then writing to disk, was slower. Well duh! That's not what memory is for!
It's not even the choice of tools, they seem to willfully misuse the languages to get poor results.
If it's in you sig, it's in your post.
SSDs and disk speed have nothing to do with this. None of these writes are hitting disk. All they've shown is that when you cache a write to disk, the operating system might add data to it more efficiently than the slow Python and Java string code can expand a string.
Let me guess
1. They used "" + "" instead of StringBuilder
2. They didn't actually flush the file bytes to disk, so it's really a comparison of stupid programmer in-memory string cat and intelligence caching of file writes.
3. They intentionally engineered a scenario that reported data that was contrary to reality in order to get clicks
Specifically, the time measured to write to memory uses the following code:
for (int i=0; i < numIter; i++) {
concatString += addString;
}
The time measured to write to disk uses the following code:
for (int i=0; i < numIter; i++) {
writer.write(addString);
}
writer.flush();
writer.close();
In Java, strings are immutable. Each string concatenation produces a new string on the heap, and the old string is unchanged. So there are numIter strings created in memory, and I assume garbage collection will probably happen at some point once enough memory is used. O(n) reads and O(n) writes to the heap with O(n^2) memory usage plus an unknown number of garbage collections. This can cause considerable slowing of the in-memory algorithm.
That algorithm is then compared with one that does numIter writes to a buffer, which is then flushed to disk at the end. O(n) writes to memory buffer (no need to re-read memory) using O(n) memory space, followed by O(1) writes to disk and O(n) disk space used.
Granted, it's been over a decade since I took algorithms so I wouldn't doubt that someone can show how I am off, but this kind of thing should be simple to spot for anyone who has an undergrad CS degree.
PS - I love how the paper makes this aside as if it doesn't matter tremendously:
Java performance numbers did not change when the concatenation order was reversed in the code in Appendix 1. However, using a mutable data type such as StringBuilder or StringBuffer dramatically improved the results.
All my liberal friends think I'm a conservative, all my conservative friends think I'm a liberal.
A more accurate title would be: "You can be sufficiently stupid with your memory access that it's faster to do disk IO."
Java is not the only system that can manifest this.
A Pirate and a Puritan look the same on a balance sheet.
The language is not the problem, the code is terrible. They did String concatenation in the most expensive way possible. I'm pretty sure if you used a pre-sized StringBuilder it would be faster in memory.
They also make some very novice benchmarking mistakes.
This is actually a pretty good interview problem. Anyone who writes code like that should not be hired, even for a junior position.
Even the slowest DDR3 SDRAM has more memory bandwidth and magnitudes faster access time.
Indeed. Their results make no sense. They are doing something weird. For instance, their paper says that concatenating a million one byte strings into a single million byte string takes 274 seconds. That should take much less than one second. Their code is listed at the end of the paper, and they seem to be assuming that "flush" means the code is actually written to disk. It does not. It just means the bytes were passed to the operating system.
The real story here, is that if you don't know how to write code properly, then string concatenation can be really slow.
Was their paper peer reviewed?
Sorry but you'll need to do it without using any memory. We need to make it fast.
Memory bandwidth is about 20Gb/s. Disk bandwidth is about 0.05Gb/s. The performance consequences of this are obvious to anyone who knows how basic arithmetic works.
The results they got are invalid because their test framework is broken. This is exactly why everyone should be forced to learn C/C++ or Assembler in college/university. The reason for the crap result is they did not preallocate their buffers so they wasted all their execution time allocating and reallocating larger buffers from the heap. The disk APIs have their own internal buffer implementations, that were not written by idiots, that manage this correctly which is the cause of the difference.
Was their paper peer reviewed?
It just was. Why do you ask?
lololol
I just scanned the paper, because their claim seem to be idiotic. It looks like they are appending a single byte on the end of a string in memory and on disk. For the memory operation, this will result in a string copy since strings are immutable, vs. doing a one byte file append onto the disk. The former is increasingly expensive and the latter is a fixed cost, so after infinite operations, the disk cost becomes far less than the memory operation. If this is indeed their claim, and I am not missing something, then they should be collectively slapped for wasting our time by writing this paper. If this is really your use case, write some proper data structures to manage your data in a sane fashion.
So yes, if you do stupid things, you can make bad engineering decisions look like good ones.
HA! I just wasted some of your bandwidth with a frivolous sig!
NEW SCIENTIFIC DISCOVERY!
For n equal to one million, an O(n^2) algorithm is slower than an O(n) algorithm. Even when the O(n^2) algorithm is run in RAM, and the O(n) algorithm is disk writes being buffered and optimized by the operating system.
I'll take my Nobel Prize now, thank you.
-
- - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
Maybe we should store our files in memory and load them into the harddrive to do calculations.
How in the world? Trivially. They're doing it in an O(n^2) way - it's the only explanation.
If you use string concat library code naively, you can end up "copy the string, add one byte, repeat" easily enough in languages like Java. And it's not exactly breakthrough research to discover that O(n) disk can be faster than O(n^2) memory for large enough n.
Socialism: a lie told by totalitarians and believed by fools.
And they're using BufferedWriter to write to the file which, as the name suggests, is buffering the data *in memory* before writing it.
So the result of the paper is actually O(n) in memory algorithm outperforms O(n^2) in memory algorithm for data sizes of 1MB. Hardly surprising.