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).
Sorry but you'll need to do it without using any memory. We need to make it fast.
'll have to dig through their testing and methods, but this seems pretty fishy given the summary.
Seek/Read/Write time of a disk is always slower than memory. No exceptions to the rule exist given current commodity hardware. Bus length to a disk is also much longer than to memory. Again, there are no exceptions given commodity hardware.
Won't be the first time someone reported that the laws of physics don't exist for something, and I'm sure it won't be the last. Maybe someone with free mornings in the US can break it down better than the summary.
-The wise argue that there are few absolutes, the fool argues that there are no probabilities.
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!
Even the slowest DDR3 SDRAM has more memory bandwidth and magnitudes faster access time.
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.
RAM *is* faster (by far) than any persistent media 9SSD, HD...). So whatever the test, the algorithm is probably bad,
Slashdot, fix the reply notifications... You won't get away with it...
on the speed of your memory, and the speed of your disk, SSD's are getting more common.
No, it doesn't. Memory is faster. If they get a result saying otherwise, they are doing it wrong, and are actually just measuring the performance of the in-memory cache speeding up the simplest implementation vs the performance of their own crappy implementation.
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.
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?
In general writing to RAM is faster than writing to the disk. However there are things that get in the way of both.
1. OS Memory Management: So you making a small memory string to a big one. So will the os fragment the string, when it comes up to an other systems reserved memory spot. Will it overwrite it (Buffer overflow), will it find a contiguous larger memory block and copy the data there. Will it copy and move the memory slots to a new location away from the memory. Will this be happening preemptively, or when the error condition occurs, will all this stuff happen with a cpu cycle that is not sharing with your app. Also if you are low on memory the system may dump it to the disk anyways.
2. OS Disk management: A lot of the same concerns that memory management has. However a bunch of small request is easier to find free space, then asking for a larger spot. So they may be more seek time.
3. Disk Caching: You tell the program to append to the disk. The OS sends the data to the drive, the drive responds back Yea I got it. then the OS goes back to handling your app, in the mean time your drive is actually spinning to save the data on the disk.
4. How your compiler handles the memory. Data = Data + "STRING" vs. Data+="STRING" vs Data.Append("STRING") vs { DataVal2=malloc(6); DataVal2="STRING"; DataRec->Next = *DataVal2; } You could be spending O(n) time saving your memory where you can be doing in in O(1)
Now sometime I do change my algorithm to write to the disk vs. handling it in memory. Mostly because the data I am processing is huge, and I much rather sacrifice speed, in order to insure that the data gets written.
If something is so important that you feel the need to post it on the internet... It probably isn't that important.
Was their paper peer reviewed?
It just was. Why do you ask?
lololol
[...] 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.
I didn't RTFA, but after reading this I am certainly not going to. This C++ piece of code takes around 0.01 seconds to run on my computer:
#include <iostream>
#include <string>
void build_string(std::string &s, std::string r) {
for (int i = 0; i < 1000000; ++i)
s += r;
}
int main() {
std::string s;
build_string(s, "a");
std::cout s.length() '\n';
}
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!
They tested using strings in python and java, both of whose string libraries are very much overweight. And they tested by concatinating strings in a way that requires constant reallocations and memory copies versus pushing data to fixed size disk buffers in the OS cache.
So... surprise! When writing data sequentially the C implementation of disk buffers is faster than the java and python implementations of strings.
Moderating "-1, Disagree" is simple censorship. Have the guts to post your opinion.
Except they don't write to disk. They wrote to an OS controlled buffer. Simply calling flush does not force a disk write. It signals the OS to take control of the buffer.
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.
That's the very first thing I thought of... what if the code were written in a lower-level language (and not in fucking python or Java!), then made do this task on Windows $latest, OSX $latest, Linux $latest, maybe a resurrected DOS $latest for reference, etc... I mean, it can't be that hard to write this thing in C and port it as needed.
Doesn't seem very scientific at all otherwise. I mean, are they testing memory versus disk, are they testing memory vs. disk performance in a given specific language, or what? Maybe they just needed to flesh out their abstract a bit more to reflect this?
Quo usque tandem abutere, Nimbus, patientia nostra?
It makes perfect sense once you read the paper. The conclusion is techniocally correct but deceptive.
The results apply in the case of Java and Python where strings are immutable objects. They also used buffered I/O handled by libc. When you concatenate immutable strings, you must allocate a new string large enough to hold both parts, then a memcpy from both of the parts is performed to construct it. The parts are eventually garbage collected.
In contrast, writing to a file with buffered I/O means just copying the additional write buffer to the current end of the buffer and moving updating the accounting information.
As a result, in both cases, only one actual filesystem transaction takes place writing out the complete string. Thus, the actual practical difference between the two methods is that the 'in memory' version copies the memory around many times while the 'disk i/o' one copies the data once (in multiple steps, but each byte sees one copy).
That seems like a bit of a no-brainer, but the point is valid because many programmers may deceive themselves into thinking the 'in memory' method is faster because they don't take the file i/o buffering and the way immutable strings are handled into account.
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.
Was their paper peer reviewed?
I believe that it may have been beer reviewed.
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?
I just reviewed it, but frankly, they're not my peers.
They actually understand the problem and state it near the end of the paper. The issue is pretty simple and when I read the /. summary I knew what the problem was. They're appending single bytes to a string. In both chosen languages - Java and Python - strings are immutable so the "concatenation" is way the hell more complex than simply sticking a byte in a memory location. What it involves is creating a new string object to hold both strings together. So, there's the overhead of object creation, memory copying, etc. Yes, by the time you're done it's a lot of extra work for the CPU.
I'm going to state this as nicely as I can: what they proved is that a complete moron can write code so stupidly that a modern CPU and RAM access can be slowed down to the extent that even disk access is faster. That's it.
Even if you wrote this in C in the style in which they did it the program would be slow. Since there's no way to "extend" a C string, it would require determining the length of the current string (which involves scanning the string for a null byte), malloc'ing a new buffer with one more byte, copying the old string and then adding the new character and new null byte. Scanning and copying are both going to require an operation for each byte (yeah, it could be optimized to take advantage of the computer's word length) on each iteration, with that byte count growing by "1" each time.
The sum of all integers up to N is N(N+1)/2. If N is 1,000,000 the sum is 500,000,500,000. So, counting bytes (looking for null) requires half a trillion operations and copying bytes requires another half trillion operations. Note that "operations" is multiple machine instructions for purposes of this discussion.
Yeah, modern computers are fast, but when you start throwing around a trillion operations it's going to take some time.
Writing to disk will be faster for a number of reasons, mainly because the OS is going to buffer the writes (and know the length of the buffer) and handle it much much better. It's not doing a disk operation every time they do a write. If they were to flush to disk every time they would still be waiting for it to finish.
There are a few notes, here. First, in Java and Python the string object likely holds a "length" value along with the actual character buffer. That would make it faster and not require all the operations the badly written C code that I describe above would require. But the overhead of objects, JVM, interpreter, etc. gets thrown into the mix. Second, if I were doing something like this in C I could keep the string length as part of a struct and at least make it that much faster. The point is that a good programmer wouldn't write code in this manner.
Anyway, this "paper" proves nothing except that really bad code will always suck. One would have to be an idiot to write anything close to what they've done here in a real-life scenario. I know because I've cleaned up other people's code that's on the level of this junk...
Do you have ESP?
There's nothing wrong with Java or Python, but the programmer is inexperienced. Java and Python strings are immutable. So, any time they concatenate a single character to an existing string, the Java runtime creates a brand new string, leaving the original string intact (since it is immutable). So if they create a million character string using using million concatenations, guess what, a million new strings are created and that's very slow. A better solution is to use a mutable String aka, StringBuilder.
But the right solution is to use a small buffer, say 16KB to 100KB in size, fill that with characters and flush that buffer to disk every time it's full. The speed would be same as any other method, but the max memory used is 20x smaller.
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.
One of them looks like a chemical engineering PhD student and the other is a tech, so maybe not. The third is an electrical engineering professor who's supposed to be doing software performance research though. He should definitely know better.
Although, when I was at the U of C the people doing software stuff in the EE department had some very interesting ways of doing things.