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).

Comments

It depends

[rossdee]

on the speed of your memory, and the speed of your disk, SSD's are getting more common.

Re:It depends

[Lunix Nutcase]

Even the slowest DDR3 SDRAM has more memory bandwidth and magnitudes faster access time.

Re:It depends

[greg1104]

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.

Re:It depends

[hcs_$reboot]

RAM *is* faster (by far) than any persistent media 9SSD, HD...). So whatever the test, the algorithm is probably bad,

Re:It depends

[Carewolf]

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.

Re:It depends

[jedidiah]

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.

Re:It depends

[aethelrick]

hehe... well said. If I had mod points you'd be getting them for making me laugh.

Re:It depends

[ShanghaiBill]

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?

Re:It depends

[Lunix Nutcase]

It's on arXiv so probably not yet. Hopefully it gets sufficiently mocked.

Re:It depends

[Anonymous Coward]

Probably not, and sadly this is the problem with current CS tracks in colleges.

Zero education on hardware gives us CS grads that are inept.

Re:It depends

[Anonymous Coward]

How many buffers sit between user code and disk?

- Application buffering?
- Kernel buffering?
- Cache controller?
- Controller buffering?
- On-drive buffering?

RAM is typically fast enough that you can't do anything too stupid with it...the researchers proved us wrong there I guess. It's going to be a lot slower if you break the pipeline - writing 1MB to RAM and then waiting for that to finish before re-reading it all back and writing it all out to disk is going to be slower. Left strictly to the kernel the whole pipeline is streamed and asynchronous. Bytes written to I/O don't block the application from submitting more bytes to I/O unless some buffer is full somewhere. So it seems that what they've proven is that doing things in parallel is faster than doing them serially for some task that's approaching embarrassingly parallel. Well then. Color me shocked.

Re:It depends

[jellomizer]

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.

Re:It depends

[Anonymous Coward]

Was their paper peer reviewed?

It just was. Why do you ask?

lololol

Re:It depends

[PacoSuarez]

[...] 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';
}

Re:It depends

[jeffmeden]

RAM *is* faster (by far) than any persistent media 9SSD, HD...). So whatever the test, the algorithm is probably bad,

I read this summary as "when the goal is to write a string to disk, building it in memory first is slower than just writing it to the damn disk in the first place".

Followed by a "does this mean my cafeteria meal card is going to get renewed?" at the end.

Re:It depends

[Anonymous Coward]

Or that, if for whatever reason your data slowly accumulates, but you are sure of the first bits of it before receiving the last, writing the bits you already know while the rest is processing is faster than waiting for it all to process then write to disk.

Re: It depends

[Anonymous Coward]

Look at the asm. I doubt that code resembles the asm.

Re:It depends

[Lunix Nutcase]

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.

Re:It depends

[TWX]

This is just a guess as I'm not a programmer but am acquainted with computer architecture...

If they're writing the string to disk and not really reading it back constantly then the act of writing could be being handed to the disk controller in chunks and effectively offloaded, which would reduce CPU time used for those sequential writes compared to the CPU handling all of the work in memory as the process goes then handing it to the disk controller only once to write it.

I don't think this would hold up if they're having to read from the disk versus read from RAM or cache, which is how I expect most real-world applications to work. Their comparison reminds me of putting an old van with an inline 6 cylinder engine on a dyno roller with almost no resistance and spinning the wheels up to 140mph, then claiming that the van is as fast as a muscle car.

Re:It depends

[meerling]

I'm not saying these guys didn't goof up in some way, or if they were right, it's just that sometimes the old paradigm of how everyone believes things work is just plain wrong.
I'll give one example from when I was in high school. As any programmers among the readers know, the slowest form of sort is the bubble sort. We figured out how to make it faster than all other types of sorts. We kind of freaked when our trick not only worked, but it made it the fastest. We then tested it and worked out an algorithm to keep it at it's fastest.
The old paradigm that bubble sorts are the slowest sorts got destroyed, so it's always going to be possible that old accepted assumptions about how things work can be overturned, even if it requires certain specific parameters. (Of course crap code will F anything, so that's not what we're talking about.)

Re:It depends

[Anonymous Coward]

Same here. Using C++, I get equivalent run times (.02 seconds) for this:

string str;
for(int i = 0; i 1000000; ++i)
        str += '1';
ofstream out("test.txt");
out str;

versus this:

ofstream out("test.txt");
for(int i = 0; i 1000000; ++i)
        out.put('1');

(If I use out << '1', then the second variant is actually slower than in memory.) How in the world could that loop be taking 274 seconds?

Re:It depends

[Bengie]

Pretty much. What they're saying is it's faster to write data strait to disk than to copy that data around in memory, then write it do disk. In other words, A is less than A + B

Re:It depends

[Rakarra]

Probably not, and sadly this is the problem with current CS tracks in colleges.

Zero education on hardware gives us CS grads that are inept.

It's not necessarily that -- I think there's a third layer that doesn't get the attention deserved while people work on end-user applications or tinker building hardware. There's not much attention on operating system design and fundamentals. Your code will usually be dealing with an OS and rarely with the bare hardware, so I'm surprised there's as little attention about operating systems principles and design.

Re:It depends

[Lunix Nutcase]

Except they don't write data straight to disk. They write to an OS-controlled buffer. Their code only forces the buffer to be passed to the OS for it to do with as it pleases.

Re:It depends

[imnes]

It looks like they're creating 1,000,000 strings (from 1 byte, up to 1,000,000 bytes). Isn't that ~ 500GB of memory allocations and releases?

Re:It depends

[Penguinisto]

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?

Re:It depends

[Penguinisto]

They used Java and Python. Draw your own conclusions from that. ;)

Re:It depends

[sjames]

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.

Re:It depends

[lgw]

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.

Re:It depends

[Beat The Odds]

Was their paper peer reviewed?

I believe that it may have been beer reviewed.

Re:It depends

[Penguinisto]

Ditto here... and GP has a damned good summary to boot.

Re:It depends

[Ronin Developer]

All else being equal, I am betting that they coded in a language that:

1) Uses the heap to allocate/reallocate memory (ie. 1 million times).
2) Uses non-mutable strings.

This will be significantly less efficient (i.e painfully slow) than writing each byte to a buffer in the HD and then committing the buffer to disk.

Snap...just read the article. They used Java and Python...need I say more.

Re:It depends

[Anonymous Coward]

Use the right tool for the right job:

Simple append case: takes 0.065s

    a=bytearray()
    for i in range(1000000):
        a.append("a")

For the prepend case: takes 0.066s

    a=bytearray()
    for i in range(1000000):
        a.append("a")
    a=reversed(a)

Of course, if you are prepending more that 1 byte, then it wouldn't work.
For the prepend case, without trickery: takes 17.72s

    a=bytearray()
    for i in range(1000000):
        a.insert(0,"a")

The paper has its merit, but any sane programmer should use the right data type for the job.

Re:It depends

[Ignacio]

That they barely knew what they were doing. But what do Java and Python have to do with it?

Re:It depends

[sjames]

It is terrible, but its 'terribleness' may be non-obvious. The paper's actual purpose is to point that trap out so people don't fall in to it. Do read it.

Re:It depends

[Megol]

I'm not saying these guys didn't goof up in some way, or if they were right, it's just that sometimes the old paradigm of how everyone believes things work is just plain wrong.
I'll give one example from when I was in high school. As any programmers among the readers know, the slowest form of sort is the bubble sort.

Wrong. It is commonly the slowest _real_ sorting algorithm but for some data it is very fast. Sorted or almost sorted data are the best cases for it.

We figured out how to make it faster than all other types of sorts. We kind of freaked when our trick not only worked, but it made it the fastest. We then tested it and worked out an algorithm to keep it at it's fastest.

For generic data that is simply impossible.

The old paradigm that bubble sorts are the slowest sorts got destroyed, so it's always going to be possible that old accepted assumptions about how things work can be overturned, even if it requires certain specific parameters. (Of course crap code will F anything, so that's not what we're talking about.)

Either you forgot to list limitations to the problem that make your assumptions above right for that _specific_ problem or you are completely wrong.

Re:It depends

[swilver]

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

Wow, this may have been the case eons ago when MMU's didn't exist, but in a modern day OS, you get an address space that's all your own. Nobody else is using it, and real memory is simply mapped (usually in chunks of 4k or 8k) into your address space -- it can be fragmented all over the place, it will still look like one nice big chunk to your program.

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

Most filesystems already work with a minimum of 4k chunks. I cast serious doubts on your claim that smaller chunks are easier to find, it would depend on the data structure used for tracking free space and whether the filesystem is reserving space for you by leaving gaps at your last write location.

Re:It depends

[Trailer Trash]

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...

Re:It depends

[DigiShaman]

Starting with Windows 8 / 2012, developers have restricted disk / volume I/O access. I'm not sure how this plays in regards to the testing, but link below nonetheless.

https://msdn.microsoft.com/en-...

Re:It depends

[Anonymous Coward]

This is not about the performance of memory vs. disk. It is about developers relying on rules that are too simple and can fail catastrophically. That is a valid real-world-concern.

Re:It depends

[Anonymous Coward]

I didn't read the paper yet, but the only way to do it right in python is with the stringio module, or perhaps with ctypes. Anything else will have huge overhead to concatenate 1 byte.

Re:It depends

[gnasher719]

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.

What are the bets that they didn't actually append a byte to a string, but created a new string consisting of an old string with one byte added?

In Objective-C, this would be using NSString instead of NSMutableString. In Java, which they were using, probably using a String instead of a StringBuilder or something similar. A file containing a string is basically a mutable string.

So the headline should be: Doing things on disk can be faster than doing incredibly stupid things in memory.

Re:It depends

[Anonymous Coward]

I know, I know, this is slashdot and we don't read no stinking articles around here... But seriously, the only thing that's crappy is your comment, because, not having read the paper, you have no clue what their results are. I did read it and let me tell you, they are correct, properly explained, and relevant to the real world. They won't win any awards for it, because it is pretty simple, though.

Re:It depends

[rrr00bb5454]

The silliness of the paper is that there is no reason at all to keep previously submitted chunks in memory, and it's like somebody discovered that naive string appends are quadratic in memory allocation. On day 2 of everybody's first job, they learn to just append strings to a list and either flatten them to the one big string you need at the end, or evict the head of the list out somewhere (disk?) when a reasonable chunk size (optimize for block size) or amount of time (optimize for latency) has passed. I would imagine that in this case, you should simply queue up writes in memory into a constant-sized and pre-allocated buffer, and flush to disk as soon as it is the size of a disk block.

Re:It depends

[TemporalBeing]

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.

Actually, you can "extend" a C-style string just fine in C - just replace the NULL byte with another byte. It's a common error in C programs to miss the NULL byte.

This works because C doesn't do boundary checks and will gladly let you overwrite your stack or heap.

Unlike Java, C doesn't try to protect you from yourself.

Re:It depends

[edtice1559]

I'm pretty sure that, in order to write something to disk, it first has to be written to memory! I don't think there is a function that goes right from a register to disk.

Re: It depends

[samkass]

Actually, even beginner Java programmers know to use a StringBuilder for these cases, which allows for constant-time appending. It's a little harder to do "right" in C and accidentally get O(n^2) time by reallocating memory each time, but still not hard. The language here isn't making the difference it's their algorithm.

Re:It depends

[suutar]

yeah. Looks like they're comparing concatenation (with all the attendant object creation and obsoletion) with the equivalent of using a stringbuffer (that happens to be held by the kernel). Shock, amazement.

Re:It depends

[Anonymous Coward]

They are fulfilling their own premise by not understanding the system in which they experiment. Between the on disk cache and os level disk caching they are in all actuallity making the writes to memory and it is only flushed to disk in 1 action at the time they flush (or perhaps before that time if the system flushes it on its own). Further the in memory tests have been constructed using heavily oo languages in such a way that they are producing extream amount of expensive ops -- from allocs, gc tracking, string concats, memory segment blowouts etc. In effect the direct to disk and the in memory concat should be around the same timeline for these tests (the os and disk cache + flush is basically the os doing the same thing as the code should be doing without the application drool factors). Things like just preemptively setting the string length can reduce the number of drool ops so very dramatically.

Re:It depends

[suutar]

This. They've discovered that stringbuffers are faster than repeated string concatenation, is all.

Re:It depends

[Trailer Trash]

Well, yeah, but that's not going to work consistently. Worst case is if the string is on the stack you'll smash the stack and likely have a memory access error. If it's on the heap you'll likely get the error quicker.

I wouldn't even think of writing a program in the manner in which their sample was written, but if I was trying to solve their basic "problem" there are better ways to go about it.

Re:It depends

[PsiCTO]

"Was their paper peer reviewed?"

I think all the other students were too busy writing exams, so no...

Okay, that's mean. To be fair, one author is a Project Manager. However, another is an Associate Professor who teaches "W2014 - SENG 533 - Software Performance Evaluation"... this is a concern for his students.

Re:It depends

[jbengt]

RTFP before you complain, it already addresses your concerns. The point is about assuming that disk write will be slower, when, in real life, some specific programs can be sped up by writing directly to disk. They mention that the OS takes care of disk buffering for you and note a lot of stuff that is happening behind the scenes in memory, especially with immutable strings in high level languages.

Re:It depends

[twitnutttt]

The study found: "For example, using Java (on both Windows and Linux) to concatenate 1,000,000 1-byte strings in-memory and doing a single write to disk was 9,000 times slower than simply doing 1,000,000 disk writes. The in-memory approach was faster when the code was written in Python instead of Java, but was still hundreds of times slower than the write-to-disk-only approach when doing many concatenations. As expected, as the number of string concatenations decreased, the in-memory approach got closer and closer to the time required by the disk-only approach."

This does make some sense, as string concatenation in Java is well-known to be an inefficient process. (Hopefully they're using StringBuffer and not plain String!) But the fact that it holds true in Python also, albeit orders of magnitude better, is surprising.

Re:It depends

[Anonymous Coward]

It's exactly this. The Java code they wrote uses String, resulting in an O(n^2) algorithm. A trivial change to StringBuilder would result in an improvement to O(n).

The paper is just embarrassing.

Re:It depends

[gnupun]

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.

Re:It depends

[V-similitude]

Indeed. Relevant text from TFA:

The explanation offered by the authors is that these higher level languages are doing a lot of work behind the scenes to handle the concatenation, such as creating new objects and copying the strings in order to accommodate the extra bytes of data. “The above explanation applies to any data structure that has to be stored contiguously and increases in size, or is immutable,” they wrote. Conversely, the disk-access approach was faster because the operating systems handled the writes efficiently via buffering and only actually wrote to disk when necessary.

They're trying to point out exactly what everyone here is trying to say they're missing. Not really sure it warrants a research paper, but yeah, common sense if you've ever studied computer science at all.

Re:It depends

[Anonymous Coward]

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.

Re:It depends

[gbjbaanb]

I think this shows the education of modern programmers.

Take a string, append 1 byte. Repeat a million times. Say "why is it so slow?".

Its probably because every time you write to most strings classes, you're making a copy and re-allocating the whole lot, and then deallocating the original.

If you knew C, you'd know what was happening here. This is why we need to teach C to programming students and not Java. Once they know C they can learn Java or whatever takes their fancy on their own time.

(although even Java and .NET programmers should understand what a stringbuilder is and why you'd use it)

Re:It depends

[AlejoHausner]

OK, so the authors are bad programmers and don't understand how string concatenation works. Strings are contiguous arrays, whereas disk files are made up of consecutive blocks, which are accessed through an index. If you want to append to a file, you may add a block, and modify the end of the index. But if you want to append to an array, you are forced to allocate a whole fresh array, because strings use fixed-size arrays.

On the other hand, Java StringBuffers have amortized O(1) append cost. A StringBuffers occasionally re-allocate themselves to larger pieces of memory, and the amortized cost of an append is O(1).

Re:It depends

[Anonymous Coward]

It's easy to explain actually...

Java strings are immutable.

This means the 'million byte string' is actually causing gigabytes of memory to be consumed, likely swap-thrashing (then triggering the GC repeatedly which is quite slow when 99% of resources end up being cleared each time) through ~500GB ((1M / 2) * (1M + 1) for the sum of 1-1M) of data Java is attempting to allocate during this program.

This is purely a matter of novice programmers having zero idea how to do this, and doing it poorly in a language renowned for having pitfalls and random traps for the unwary. And hey... they stumbled neck-deep into one!

- WolfWings, too lazy to log into SlashDot in around a decade now...

Re:It depends

[ndykman]

It doesn't warrant a paper. This is basic algorithms. They deserve all the ridicule they get, and I hope it is a lot.

Re:It depends

[BarbaraHudson]

Anyone with any brains would have pre-allocated an array, then written into it at the appropriate offsets. These people are idiots.

Re:It depends

[Darinbob]

The actual report had other factors involved. Ie, it kept growing a string using a high level language like Java or Python. Thus the underlying runtime system would have to keep growing the string, freeing and reallocating memory, exacerbating garbage collection frequency, etc. Meanwhile the file system is happily buffering all the writes. My guess is that on a similar system using C that the smart programmer isn't going to see these effects, either by relying on the file system to do buffering or else use a fixed size buffer.

Re:It depends

[Darinbob]

Yes, the code is goofy. They're in a very high level language. If they concatenate a million one byte strings one at a time, then there's one million strings that have been created. Ie, reallocate the memory constantly, keep the garbage collector busy, and so forth. Ie, the effort in trying to get the entire contents in memory being build up incrementally was slower than the actual I/O time. Ie, 4 minutes versus a fraction of a second. Meanwhile if they had just written one byte at a time to the file system then both Windows and Linux would happily buffer up that data and write it out much more optimally.

Re:It depends

[Arancaytar]

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

wtf. The only way it could take that long would be if they were concatenating them as immutable strings and had to copy the result repeatedly.

Re:It depends

[Anonymous Coward]

You're right, I took the java code from the paper, added some more logging and ran it.
Basically hung for a few minutes on the "in-memory" part of the first iteration.
Changing this
                        String concatString = "";
                        long startTime = System.currentTimeMillis();
                        for (int i = 0; i numIter; i++) {
                                concatString += addString;
                        }
to
                        long numIter = totalMemory / addString.length();
                        StringBuilder concatString = new StringBuilder(addString);
                        long startTime = System.currentTimeMillis();
                        for (int i = 0; i numIter; i++) {
                                concatString.append(addString);
                        }
yielded following output (whole test done in matter of seconds:
In-memory mean: string time 0.017300000000000003
In-memory mean: file time 0.010899999999999998
Disk-only mean: file time 0.0984

Optimizing further, extending initial capacity of stringbuilder to the required size didn't really add performance increase.

It seems to me the above code was used in a graph on their paper to prove the worst case scenario of a 10.000x (!) slowdown using stringlength 1.
Small tweak just added a 30.000x speadup, whodathunkit.

Doesn't seem like good publicity for the University of Calgary...

Re:It depends

[Anonymous Coward]

I'm thinking something wasn't accounted for:
- Disk Cache (as in OS)
- DISK cache (as in the 16-64MB mechanical drives have)
- SSD speed
- CPU Cache.

It mentions Java and Python, which means that the interpreter would have optimized things that they haven't seen. Just consider how variables are handled in these languages versus straight C.

Re:It depends

[ceoyoyo]

They're not doing something weird, the article is crazy.

Basically, they wrote some shitty code to do highly inefficient string concatenation and, wow, it turns out that it's less efficient than the caching code in the operating system. They're not comparing in-memory versus disk operations at all.

Re:It depends

[ceoyoyo]

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.

Re:It depends

[ceoyoyo]

The Python code

s = ''
for i in range(0,1000000):
    s += str(i)

will be painfully slow too, for multiple reasons. Both Java and Python have ways to do this that aren't dumb.

Re:It depends

[pjt33]

It is bad, but I've seen worse.

Re:It depends

[Anonymous Coward]

It doesn't warrant a paper.

Why? If you were trying to argue it is not appropriate for a particular journal, that would be one thing. But this is just thrown up on Arxiv, which includes papers varying from blog level commentary to course notes to student projects. It is just a short paper explicitly stating that stupid or contained coding examples can break rules of thumb, and that it is important to know something about underlying mechanisms.

Re:It depends

[Pseudonym]

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.

Which is to say, do what every programming language with buffered I/O does.

Re:It depends

[Pseudonym]

Also relevant text from TFA:

In this paper we use code inspired by real, production software [...]

Sadly, that's probably 100% accurate.

Re:It depends

[Atzanteol]

They did do it with StringBuilder also - and showed a large improvement. It's like they read your mind!

Re:It depends

[Atzanteol]

Didn't read the paper eh?

Re:It depends

[Atzanteol]

In the Java application they're using a BufferedWriter as well - so they're buffering before the OS buffer.

It seems pretty clear to me that "concatenating a string then writing it to a buffer and flushing that to disk" would be faster than "writing a bunch of strings to a buffer then flush that to disk." They're basically copying that data around at least twice.

Re:It depends

[Anonymous Coward]

If that's your idea of "extending a string" then perhaps you should be using a language which protects us from you, er, I mean you from yourself.

Re:It depends

[chuckugly]

Actually the way they did it, when you write to a file you add a byte to a memory buffer and the runtime and/or OS and/or disk controller will then write that across the IO bus to cache in the disk, where it will finally get carved into the platter. I believe.

What they are doing is exploring two different ways to concatenate in memory, one using Java and one using lower level code written in (probably) C.

Re: It depends

[Anonymous Coward]

Actually, experienced Java programmers know that the compiler uses StringBuilder internally.

Re:It depends

[Atzanteol]

Which makes it very strange that they would think to write a paper on it. It's not even worth a blog post.

Not to mention that in the Java implementation they're writing to a BufferedWriter. So even with the StringBuilder they're comparing "concatenating a string, writing it to a buffer and writing that to disk" to "copying strings to a buffer then writing that to disk."

If you do more work it takes longer. QED.

Re:It depends

[Quatermass]

There will be a mass of garbage collection....Slow, very slow.

Re:It depends

[31eq]

The simple way to do it in Python is

>>> import time
>>> import random
>>> chars = [chr(random.randint(0,255)) for each in range(1000000)]
>>> stamp=time.time(); joined=''.join(chars); time.time()-stamp
0.11153912544250488

So that's 1/9 of a second on a not very fast laptop. You can try it yourself. Obviously not as fast as C++ but not horrible.

Re: It depends

[Anonymous Coward]

A million bytes is 1MB. Assuming that the new string and old one are all that are kept around, they would be using just under 2MB in the last calculation.

Using gigabytes of memory is unlikely unless the language had terrible garbage collec... Oh, yeah: Java.

Re:It depends

[irbishop]

If they had bothered to learn anything about the language they would have discovered that the python wiki explicitly states they're doing it wrong:

Avoid this:

s = ""
for substring in list:
s += substring


Use s = "".join(list) instead. The former is a very common and catastrophic mistake when building large strings.

Re:It depends

[WolfWithoutAClause]

Yeah, and if you think about it, the OS's disk buffer is an array and it's already allocated. ;)

Re:It depends

[bingoUV]

The above explanation applies to any data structure that has to be stored contiguously and increases in size, or is immutable

But it was never necessary for the "in memory operation" (their words) to use an immutable data structure. If you use bad data structure when using in-memory, of course in-memory will be slower than disk.

Re:It depends

[NoOneInParticular]

They're testing the common assumption that to do anything fast, you have to do it in memory, regardless of language etc.They take production code to test this. Their work falsifies the claim that memory operations are necessarily faster. The abstract is pretty clear about this, not sure where you got confused.

Re:It depends

[DeKO]

Replying to undo accidental moderation.

Also, the python code is a prepend (concatString = addString + concatString) to force a quadratic algorithm, when doin in-memory; which is completely different from the direct-to-file append. When they changed the order, to compare append vs append, in-memory-then-file was faster.

Re:It depends

[bingoUV]

But except saying it "dramatically" improves results, the StringBuilder result wasn't worthy of a mention or a compare against disk performance.

Obviously, like any good "researcher" does, the conclusion was written first and then the "experiment" was performed. Any results contradicting the conclusion have to excluded.

Re:It depends

[ILongForDarkness]

Yeah I'd say bad implementation. They could have some performance improvement depending on timings and such though. Messing around in memory + one fairly large (only 1MB so not really but lets say for arguments sake) vs many smaller writes depending on how the OS handles the write requests you might end up hitting the disk cache and then doing work while the disk is busy spinning and actually writing out your changes. With one big write you might end up hitting some limit that makes the thing not fully buffered in cache and have to wait for the disk to actually complete the write.

Re:It depends

[gnupun]

The point is about assuming that disk write will be slower, when, in real life, some specific programs can be sped up by writing directly to disk.

No, you can't speed up something by using something that is at least 10,000 times slower than the alternative.

// Second part: disk-only
try {
writer = new BufferedWriter( new FileWriter("test.txt"));
startTime = System.currentTimeMillis();
for (int i=0; i < numIter; i++) {
writer.write(addString);
}
writer.flush();
writer.close();
endTime = System.currentTimeMillis();

Their so-called code that "directly writes to disk" in fact writes several KB to memory (using a BufferedWriter object) and then writes that memory to disk at several intervals. So their argument that disk-based code can be faster than memory-based code is completely false in this case.

This is what the javadocs for BufferedWriter state:

Writes text to a character-output stream, buffering characters so as to provide for the efficient writing of single characters, arrays, and strings.

The buffer size may be specified, or the default size may be accepted. The default is large enough for most purposes.

Re:It depends

[Anonymous Coward]

I think the reason that this has gotten so many angry responses from people who seem to be missing the point of the paper is that the point of the paper is so blindingly obvious to anyone who has ever studied CS. People have a hard time comprehending or believing that could be the point of the paper at all.

Re:It depends

[sjames]

Quite possibly. Sadly, I'm not so sure about the number of people who studied CS who find this obvious. A lot of people see a bunch of f.write and think I/O, must be a faster way.

Re:It depends

[Anonymous Coward]

The paper is just embarrassing.

^^ This.

Re:It depends

[Anonymous Coward]

Their work falsifies the claim that memory operations are necessarily faster.

Except it doesn't; it shows that doing a shitload of work in memory can be slower than doing fewer operations direct to disk to achieve the same result.

Re:It depends

[Arkan]

Exactly this! And for the java part at least, they should use NIO channels, which are designed to be closer to the system.

What they determine, in fact, is that their coding knowledge is sub-par. Not to be unexpected from people in biological sciences!

The real issue is: how come Slashdot editor didn't saw this as soon as the story was submitted and put it back where it belongs: /dev/null?

Re:It depends

[Anonymous Coward]

It could be some naive version without memory pooling etc. or the pooling was disabled. Reallocation of memory each time a new character is added would make sense.

Re:It depends

[Anonymous Coward]

One would not have to be an idiot. One would only have to be inexperienced. It's a shame that your experience makes you think less experienced people are "idiots". Some guys will read this paper and have a "woah!" moment just like all those "woah!" moments we had in the 90s which enable us now to see how straightforward this paper is. Until you do that, though, there's no underlying reason to assume that the simple and basic operation of concatenating strings happens to be very poorly implemented in most/all languages. The fact is, the programmer should be able to write that code and the compiler should be able to make it run fast. String concatenation is so fucking basic it's actually a real shock that basically no language has proper support for it. It's like language designers are all idiots.

Re:It depends

[Carewolf]

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,

There is. It is called realloc. If you are unlucky, it will just divide the number of times the system actually performs by 16 or whatever the malloc implementation uses as an alignment, but once the allocation gets big enough you get a pages directly from the system, and it just maps in more pages on the end.

Re:It depends

[Trailer Trash]

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,

There is. It is called realloc. If you are unlucky, it will just divide the number of times the system actually performs by 16 or whatever the malloc implementation uses as an alignment, but once the allocation gets big enough you get a pages directly from the system, and it just maps in more pages on the end.

malloc isn't the problem, though. My point was that if you write it in the style of the code in the paper (don't keep track of the string length between character appends) then it'll still have to scan the string a million times. If you know ahead of time that you're going to append exactly one million characters to the string then you need but one malloc, right? I can make this program extremely fast in that manner but that's not what they're doing.

Re:It depends

[Anonymous Coward]

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.

Why does the buffer need to be reallocated for each new byte? I would realloc the buffer doubling the size each time it overflowed. This allocation strategy is simple, is bounded to 50% worst case overhead, and requires only log N reallocations for a maximum buffer size of N.

You also don't need to scan the string, as this is an obvious case for memoisation.

Re:It depends

[cinky]

They are shitty devs, that's my conclusion...

Re:It depends

[rioki]

This is only an iteration of sibling posts, but they are using the most retarded solution to build a sting in memory. Something that you learn in your introductory course, use StringBuilder, because performance...

Re:It depends

[rioki]

Actually I think with modern OS and compiler the opposite is true. The moment you overwrite your stack canaries and return address you app goes *poof*. (No message box, no error handler, just disappears from the process list.) You can live with corrupted heap objects for a good while; especially if you wrote over the
end and don't try to free / reallocate the following heap object.

Re:It depends

[sjames]

Because StringBuilder works so well in Python?

Re:It depends

[Anonymous Coward]

summation(0 -> n) = 0 + 1 + 2 ... n
O(n)

summation(0 -> n) = (nn + n) / 2
O(1)

Re:It depends

[TemporalBeing]

If that's your idea of "extending a string" then perhaps you should be using a language which protects us from you, er, I mean you from yourself.

It was meant a counter to the GP saying that it was impossible to "extend" a string in C .

Not saying it's the correct way to do it, just that there are possibilities that the GP did not even consider, probably b/c they were taught to program using a language that protects them too much.

Re:It depends

[TemporalBeing]

Well, yeah, but that's not going to work consistently. Worst case is if the string is on the stack you'll smash the stack and likely have a memory access error. If it's on the heap you'll likely get the error quicker.

I wouldn't even think of writing a program in the manner in which their sample was written, but if I was trying to solve their basic "problem" there are better ways to go about it.

That depends on your program, and how much memory was allocated and when it would get detected. The OS is not going to detect anything until you try to leave the bounds of the program itself. Take the following function for instance:

void runOverBuffer(void)
{
char* buffer[10]; // 10 bytes
char* buffer2[1*1024*1024*1024]; // 1 GB
...
}

You can extend buffer into buffer2 without any detections going off, or even any ill-effects until you surpass buffer2 and all the other variables in the function.

Heap allocated functions are a little more tricky but even then you can produce the same kind of behavior if you really wanted to - even with the HEAP randomization, which really doesn't protect the program internally, it only protects the program from the libraries the program uses by randomizing where they are loaded.

And since you control the program, you can control the optimizations so that the only that would mess you up - by re-arranging variables - are not run.

As I pointed out elsewhere, the point is not that it's the right way to do it. It's that it is possible to do in C, just as possible as in Assembly.

Re:It depends

[unrtst]

Snap...just read the article. They used Java and Python...need I say more.

Yes. You and everyone else I've read thus far should be saying just a little bit more.

Their python example is doing this for in memory concatenation:

for i in range(0, numIter):
  concatString = addString + concatString ... but this for the disk-only version:

for i in range(0, numIter):
  f.write(addString)

Those are not the same. Try doing the same with the disk-only version (PRE-pending the value).

They even mention it and provide the corrected code for the in-memory version:

for i in range(0, numIter):
    concatString = concatString + addString

When using that, it performs virtually the same as the disk-only solution.

Granted, your point still stands, and they note that in their paper (it's pretty much the whole point of the paper). I just think comparing two completely different things is pretty stupid and worth noting.

Re:It depends

[Anonymous Coward]

Actually, you can "extend" a C-style string just fine in C - just replace the NULL byte with another byte. It's a common error in C programs to miss the NULL byte.

I don't think that's what he meant by extending a string, but the bottom line is, if you need to make your string longer than will fit in its allocated memory, you need to allocate more memory regardless of whether you do it manually or the language takes care of it.

As for omitting the null byte termination, when I programmed in C I used to use my own custom string structs, combining Pascal-style length and null termination:

struct Str32 {
      int length;
      char text[32];
      char term; /* init to '\0' */
}

I used 32-byte, 64-byte, and 256-byte versions predefined and custom versions for longer strings. The same functions handled all of them with minor tweaking. Reading the length element made it damn quick.

Re:It depends

[Anonymous Coward]

So they determined that the operating system is faster than their code.

Stop the presses.

Re:It depends

[nctritech]

It's not a programming problem, it's a programmer problem.

Re:It depends

[jeremyp]

You didn't read their paper properly. They make exactly the point that you are making. i.e. that "writing to disk", in most cases, does not mean physically writing individual bytes to the disk. The abstractions provided by both the language and the operating system help to make the obvious implementation as fast or faster than naive programmer created optimisations. In other words, this is a confirmation of the saying

premature optimisations the root of all evil

There is a WTF in the paper and it is their claim that Python doesn't run in a VM.

Re:It depends

[Eunuchswear]

No, in the case of the "paper" cited it depends on the gross stupidity of the algorithm.

They're comparing:

string s = "";
for (1..1000000) {
  s = s + "x";
}
write (x);

With

for (1..1000000) {
  write ("x");
}

For fucks sake!

Re:It depends

[Eunuchswear]

They prove that string concatenation (in memory) is slower than writing to buffers (in memory).

I.E. that :

char *s, *new;
new = malloc (len + 1);
memcpy (s, new, len);
new [++len] = 'x';
free (s);
s = new;

is slower than:

buf [len] = x;
if (++len > sizeof buf) {
  write (out, buf, len);
  len = 0;
}

What a fucking joke.

Re:It depends

[Anonymous Coward]

Would it be correct to assume that std::string allocates extra memory for resizing purposes? I.e. On iteration 22 string s actually has space for 32 characters, and when it hits the limit it expands that to 64, and so forth... that would explain why it's so much faster, since you're only doing a handful of expensive copy operations.

The new antipattern

[ubergeek65536]

Sorry but you'll need to do it without using any memory. We need to make it fast.

Re:The new antipattern

[Anonymous Coward]

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.

Re:The new antipattern

[Anonymous Coward]

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.

Let me convert this real quick...0.05Gb/s is either 50MB/s, if you wrote it incorrectly, or 6.25MB/s in the case you really did mean little b.

Are you trapped in the previous millenium? Most USB2 devices can write at >6MB/s and USB3 devices write at almost 50MB/s. Good SSD's nowadays will write at 200-400MB/s+ and spinning drives will hit 100MB/s. Current high speed DDR3 hits a ceiling around 17GB/s. All of those numbers are big B, so multiply by 8 (if you know basic arithmetic) for little b values.

http://blog.laptopmag.com/whats-the-best-ssd-5-drives-tested/2

Re:The new antipattern

[Anonymous Coward]

I'd say this more exactly why we shouldn't allow idiots to publish papers on Slashdot. I'm confident that the average person doesn't need to know the ins and outs of memory allocation and would not see any benefit for learning them. In fact, it's a relatively small group that do.

Re:The new antipattern

[Anonymous Coward]

I came here to say just that.

I recently got a Master's Degree in CS, my line of research being mathematical optimization, and I was shocked when I found out that a lot of people in those environments code their algorithms on Java, Python... even C# (!). Only a small fraction of us used C/C++. Interstingly enough, we were the ones producing the better papers.

Re:The new antipattern

[tricorn]

I wouldn't say the results are invalid, but the relevance is restricted to people who don't understand algorithms or statements such as "disk is slower than memory".

I once had to fix a program that was reading all the file names in a directory into a linked list, sorting it (using operations to retrieve, remove, and insert elements using an index, which worked by starting at the beginning of each list and counting elements until it got to the correct one), then using the resulting sorted list to process the first 10 files.

Rather than fix the abominably slow sort, I used the fact that all the file names were decimal numbers, and all the numbers were sequential, to scan the directory for the smallest number, then just increment that to find the next one. Needless to say, it was both much faster and used very little memory.

Algorithms matter, and the shame of ever faster processors and "more productive" languages is that too many programmers don't understand them.

Re:The new antipattern

[Anonymous Coward]

Isn't that the real lesson here? The guys who wrote the kernel are not-idiots to a greater extent than the guys who wrote your string library. Lean heavily on the kernel before you lean heavily on your scripting language.

Check their work or check the summary?

[s.petry]

'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.

Re:Check their work or check the summary?

[LordLimecat]

Tl; DR:

They used python and java. Sort of hard to develop a meaningful thesis on general programming when you're that far up the abstraction stack. Who knows, maybe python and Java suck at memory management (GASP).

Re:Check their work or check the summary?

[s.petry]

Not to Karma whore, but I already see two problems with their testing by reading their code samples. Lets see who else finds them. The simple answer is no, disk is not slower than memory. The long answer is yes, programmers can make it look that way.

Re: Check their work or check the summary?

[Anonymous Coward]

If I've wanted to speed an application up, I've always moved disk I/O to RAM. Especially for small data which is constantly requested from SQL. You'd have a difficult time proving disk I/O is faster to me even with SSD. The only scenario being low memory machine where swapping may be occurring (i.e. buy more RAM cheapo!)

Re:Check their work or check the summary?

[Anonymous Coward]

My guess is they're writing to write through cache and don't even know.

Re:Check their work or check the summary?

[s.petry]

read their code, you will see the problems.

Re:Check their work or check the summary?

[MightyYar]

The worst is that they DO know, and yet still wrote a whole paper on it. They are concatenating strings in Java and Python - which is slow. Surprise, surprise, it is faster to write strings to a pre-allocated buffer, in this case the disk cache. That is the whole paper.

Re:Check their work or check the summary?

[topology]

More than likely its employing concurrency between computation and buffered writes to disc. This is really just a special case, a specific exception to a good principle.

You have 2 processes. The first process is a bit-generator which generates a bit at a time for as long as needed. The second process is a buffered writer to disc.

All I got out of the summary was that it is faster to stream the output of the bit generator to the buffered disc writer than to collect all the output of the bit-generater to an in memory storage and then stream the in memory storage to the buffered disc writer. WELL DUH. No mystery there. Stream processing 101.

Re:Check their work or check the summary?

[Anonymous Coward]

The simple answer is no, disk is not slower than memory.

Yes, it is. Even the fastest consumer SSDs have access times of around .1 ms while at worst DDR3 SDRAM has access times in the low 10s of nanoseconds and has faster throughput.

Re:Check their work or check the summary?

[TheCarp]

Except that frictionless spherical cows are not realistic even if they are very helpful in physics.

When is the last time you actually talked to raw hardware? if its recent, you are a special case, and likely write drivers....in which case, good for you.

When you write "to disk" you are working in memory because its going to be a buffered access, likely reads as well, especially if it is something you recently wrote.

Exceptions will exist but, they are exceptions to the rule.

Re:Check their work or check the summary?

[Frnknstn]

It's not even the choice of tools, they seem to willfully misuse the languages to get poor results.

Re:Check their work or check the summary?

[Anonymous Coward]

RTFA. The authors explain, allocating more memory and copying bytes as the cause for slower performance. Any decent developer knows what goes on behind the scenes and takes it into account when dealing with resource intensive programs. Basically this is a non-news.

Re:Check their work or check the summary?

[Anonymous Coward]

You don't even have to read the code. Reading what languages they used reveals the entire flaw. They used languages with expensive string operations when done in-memory which is the only reason why writing to a buffered cache and writing to disk is faster.

Re:Check their work or check the summary?

[wonkey_monkey]

That is pretty much what the article suggests. Concatenating string involves creating objects, blah blah blah...

I doubt you'd see the same "9000 times slower!" kind of results with standard C strings.

Re:Check their work or check the summary?

[gstoddart]

Somewhat off-topic, but somewhat related:

Many years ago, when I was doing my degree and computers were still steam powered, a friend and I were writing the same assignment.

He worked for the university, and had a privileged account on the VAX. I had the loan of a 286 from a prof who no longer needed it and took pity on me.

I, being constrained by physical memory, had to write a new kind of sparse array to hold my data. He, having access to lots more virtual memory heap than I, wrote a huge array which wasn't sparse to just brute force it, even though most of the array was useless.

At the end of the day, we both got the same results from our programs. The difference was, I got an A+, because the prof decided he'd steal my sparse array for his own research. My friend got an A, because he got the right outcome, but used a slightly less elegant solution.

Optimizing memory is a dying skill, and in the case of most high level languages, there's too many layers between you and the hardware to know what is actually happening.

But some of us still think back nostalgically to when having a 1MB string was simply not possible, and when we used to have to use our own voodoo to cram into the small amounts of memory we did have. :-P

Now get off my damned lawn with your big fancy strings. ;-)

Re:Check their work or check the summary?

[squiggleslash]

No, it's completely understandable and shouldn't even be thought of as strange to seasoned programmers.

The critical issue is there's a difference between calling an I/O function like write, and actually manipulating the IDE control lines on a hard disk. Typically for the former, the operating system is sitting there buffering things up in a relatively simple, uncomplex, way - ie it has some memory allocated, a pointer, and when you call the function all it does is copy the bytes to the memory and increment the pointer as needed. Once either enough time has passed, a critical function has been called, or enough data has been written, the OS then starts manipulating the IDE control lines to write the data.

Now, the comparison becomes "the OS's buffer handling" vs "Your language of choice's string handling and garbage collection algorithms." For C, chances are you're as good as the OS as C's string handling is extremely uncomplicated and bare metal. For almost anything else - such as Python and Java, both tested in this scenario - you're likely to end up with the OS handling some situations more quickly than your language would.

Does it make sense now? It should. There are very few programmers this should surprise. Unfortunately, I know quote a few that will be...

Re:Check their work or check the summary?

[Anonymous Coward]

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

Re:Check their work or check the summary?

[s.petry]

Bah, I wrote the wrong thing...

The simple answer is no, disk is not faster than memory.

Re:Check their work or check the summary?

[Lunix Nutcase]

Why bother? Their entire "research" is bogus. Everyone knows that buffered writes are going to be faster than doing byte-by-byte writes.

Re:Check their work or check the summary?

[Lunix Nutcase]

Pretty much. This entire article is basically saying that if you do things in the most stupid way possible you can make it slow.

Re:Check their work or check the summary?

[s.petry]

Yup yup, I wrote something contrary to my original post quite unintentionally. Memory is always faster than Disk, unless you write shit tests that behave abnormally to make a bogus claim.

Re:Check their work or check the summary?

[greg1104]

It's all operating system cached writes, they're not even getting to the disk's write cache.

Python's file flush() function does not flush data to disk. You have to call os.fsync(f.fileno()) for that.

Same problem with the Java code. flush doesn't make sure data is on disk. You have to use sync or force or something.

This is an excellent way to introduce the smart scientist/moron coder archetype to people though, so it's not completely useless.

Re:Check their work or check the summary?

[bondsbw]

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.

Re:Check their work or check the summary?

[aethelrick]

This was of course compounded by the fact that they did not follow the languages own guidelines with regard to string concatenation. Nor did they demonstrate any clear understanding of how modern operating systems works. Sadly this was an all round a poor effort.

Re:Check their work or check the summary?

[w3woody]

Really, what's happening is that they're performing repeated concatenations of various length strings--an operation that eventually becomes O(m*n) time, with m being the length of the string and n being the number of strings. (Concatenating strings in Java requires a new string to be created, then the contents of the two source strings copied into the new destination.) Appending a file, on the other hand, is only an O(n) operation, but has a very large constant time associated with it. So, in essence: TL;DR: O(n**2) operations can be slower in memory than O(n) operations on disk for large values of n.

The real lesson is that you should understand what's going on underneath the hood. And in this case, if you're doing a lot of string concatenation operations in Java, you probably should be using the StringBuilder class. I mean, after all, that's why there are multiple ways to do the same thing in Java (like ArrayList verses LinkedList): each offers different performance characteristics, and at the fringes performance characteristics can kill your application.

Re:Check their work or check the summary?

[danlip]

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.

Re:Check their work or check the summary?

[halivar]

1. Eyup.
2. They actually did flush.
3. Absolutely.

Re:Check their work or check the summary?

[P. I. Staker]

I actually think the paper is relatively readable, easy to understand, and complete in it's explanation (not to mention pretty short). They explain exactly why they got the results they did, and what can be done to improve the in-memory version. This is an argument against expecting code to automatically be faster when executing in memory. Basically, they found that the overhead of performing string operations, using standard methods in high level programming languages, caused the in-memory performance to be poor. No part of this paper is trying to claim Seek/Read/Write time of disk approach that of memory. The authors are telling you to take the full system and programming language considerations into account and not assume in-memory means faster, especially now that systems with tons of memory are becoming common.

Re:Check their work or check the summary?

[Lunix Nutcase]

Flush in Java doesn't actually force the OS to write to disk.

If the intended destination of this stream is an abstraction provided by the underlying operating system, for example a file, then flushing the stream guarantees only that bytes previously written to the stream are passed to the operating system for writing; it does not guarantee that they are actually written to a physical device such as a disk drive.

Re:Check their work or check the summary?

[gstoddart]

I think what they've proven is that there are so many layers in modern programming languages that most of what programmers do because it seems like a good idea probably generates terrible outcomes.

This actually explains a lot about modern programs, and how 5 years later a machine with twice the resources takes the same amount of time to do something as 5 year old software.

Because the bloat and inefficiencies added in those five years offset any other improvements. :-P

Re:Check their work or check the summary?

[waterford0069]

And the Python gets even worse when they prepend `addstring` instead of appending it; making the in memory inherently different from the to disk test.
catString = addString + concatString # modified: concatString = concatString + addString

Re:Check their work or check the summary?

[halivar]

And this is why we should not teach CS101 in Java or Python. If they'd been forced to use C this whole experiment would have turned out differently. Even the professors are getting lazy, now.

Re:Check their work or check the summary?

[Jerry Atrick]

The direct disc write should also manages to overlap write to the stream object with flushes from it to the underlying drive. Except of course it doesn't because they aren't writing enough data for the disc write to actually start before they're done. I'm also a little confused about why they think flush+close is synchronous, it's going to return instantly and flush data in the background. So they aren't even timing what they think they are.

Back in the world of programmers with a clue, I did fix an in-memory piece of insanity like this not long ago. Making buffer expansion allocations more aggressive got a 10,000x speed improvement.

Dumb concatenation is for lazy or dumb programmers. Programmers that lazy probably could benefit from using more efficient append ops in the streaming libs, even if they don't understand why it works.

Re:Check their work or check the summary?

[wardeana]

Actually 'modern' (last few years) Java compilers will change that += behind the scenes to a StringBuilder / StringBuffer so that really shouldn't have any effect... agree that it used to be horrendously bad to do that though.

Re:Check their work or check the summary?

[halivar]

I stand corrected. And I assert that a professor of CS from Calgary or BC should know better than me, anyhow.

Re:Check their work or check the summary?

[Anonymous Coward]

Fixed their code by using a StringBuilder and moving the flush call inside the loop, so it actually writes it to disk.
The result:

In-memory mean: string time 0.008900000000000002
In-memory mean: file time 0.0034000000000000002
Disk-only mean: file time 1.1747

Yes, it's still quicker to do things in memory, you just have to do it right.

PS: with just one flush:
In-memory mean: string time 0.0091
In-memory mean: file time 0.0038000000000000004
Disk-only mean: file time 0.026599999999999995

Still faster in memory.

Re:Check their work or check the summary?

[PRMan]

Plus is faster if you are not in a loop.

Re:Check their work or check the summary?

[chilenexus]

Seek time alone is always slower than memory, even before you add in the latency and read/write times. It's disturbing to me that this article calls referring to memory being faster an "assumption". In college they had us do the math on paper to figure out the average latency and read times for a given RPM, and how they come up with the average seek times. The only assumption being made is that the manufacturer is honestly reporting figures accurate to a single order of magnitude.

Re:Check their work or check the summary?

[rjstanford]

Have you ever read Programming Pearls? Full of great examples of how to do elegant work with no resources that apply just as much today (just prepend "giga" to all of the numbers they use). From your comment I think you'd enjoy it.

Re:Check their work or check the summary?

[devent]

All they did compare was one memory access vs. another memory access, and showed that Strings are inefficient compared to a byte array. Because the first code will concatenate Strings in memory, the second code will concatenate byte array data in memory, and then both are written to disk. The disk-access test should have been:

    for (int i=0; i numIter; i++) {
                    writer.write(addString);
                    writer.flush();
                    writer.close();
    }

Re:Check their work or check the summary?

[bwcbwc]

And there goes another grad student's research thesis up in smoke. CS departments need to have more courses that distinguish between abstract theory (raw algorithms) and software engineering (practical effects of choosing specific languages and features). It's clear the authors of this are in an ivory tower where every string type is the same type of construct in every language.

Re:Check their work or check the summary?

[Lunix Nutcase]

Except any half-decent Java developer uses Stringbuilder not + concat because everyone knows the latter is slower and causes more to be objects created. The only thing they proved is by purposefully doing something wrong you can make it crappy.

Re:Check their work or check the summary?

[Anonymous Coward]

I don't agree with that. What I would say is for a junior position, the candidate should be able to see why it's flawed.

Re:Check their work or check the summary?

[Anonymous Coward]

Changed Java code to use StringBuilder instead of String += String. Results on my machine:
1: 0.010625
10: 0.002375
100: 0.001

Maybe somebody who study Chemical and Biological Science is not good developer

Re:Check their work or check the summary?

[Lunix Nutcase]

But they didn't do direct disk write. They merely flushed to disk cache handled by the OS.

Re:Check their work or check the summary?

[CanadianMacFan]

In my first year of engineering I had a class in assembly but on a simplified processor simulator. I learned quite a lot on it because you saw how everything got modified by your commands. The lectures were terrible because the prof told the same jokes from the book that he wrote. I still have the software somewhere but it's on a 5.25" floppy.

Actually it's on my project list to create a similar program for the iPad if I ever get the time or the help to do it.

Re:Check their work or check the summary?

[Lunix Nutcase]

Except everyone alreadys know that using that method of string concatenation is slow. This paper was just pages of waste for what is a one sentence guideline: "Use Stringbuilder to more efficiently do string concatenation." But any compentent Java programmer already knows that.

Re:Check their work or check the summary?

[Anonymous Coward]

They're not CS profs. They're not even in CS. Look at the PDF of the paper and what depts. they are actually in. One is a biologist, one is a chemist or biologist, and one is an electrical or computer engineer.

Re:Check their work or check the summary?

[VGPowerlord]

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.

What's worse is that there are warnings all over the 'net to not use string concatenation in a loop in Java. So, despite these warnings, they did that anyway and tout incorrect assumptions based on their faulty testing.

That's without even considering the other flaw you pointed out (not flushing after each write).

Re:Check their work or check the summary?

[gstoddart]

No, but suddenly I'm intrigued.

Sometime's it's tough to explain to the kids these days why they take too damned much for granted with their languages.

I knew a guy with a Masters in CS who loudly proclaimed optimizing was a pointless exercise.

He wrote some of the shittiest, slowest, and un-maintainable code I've ever seen because he was confusing "clever" with "smart" and often "clevered" himself into corners he couldn't get back out of.

Often he couldn't make minor changes to his own code because it was so "elegant" as to be brittle and impossible to change.

Very often the attitude of "the library does everything, let it deal with it" means you have no idea of how bad the code you're writing actually is.

Re:Check their work or check the summary?

[Anonymous Coward]

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.

On the upside, at least they documented what they did!

Also, they are from a biology department, what do you expect?

Re:Check their work or check the summary?

[Anonymous Coward]

We have so many different programming languages, sometimes it may not be writing to disk that is faster, but it might be moving to a different language, or changing the algorithm so it sucks less.

This was something learned early on with sorting, where the worst algorithm was to randomly order a list, and keep doing so until the list was in order O (2^n), then bubble sort with O (n^2), and finally quicksort with O (n log (n)).

If I were getting better performance writing to disk than to RAM (barring an out of memory condition), I'd be looking at a lot of other mechanics, and maybe even try a different machine to run stuff on to eliminate things like issues with a hypervisor and such.

Realistically, I should be just offshoring the job to Tata anyway, as I suck as a programmer in general.

Re:Check their work or check the summary?

[Coryoth]

And this is why we should not teach CS101 in Java or Python. If they'd been forced to use C this whole experiment would have turned out differently.

Not at all. If you wrote your C in memory string handling as stupidly as they wrote the Python and Java you will still get worse performance in C (e.g. each iteration malloc a new string and then strcpy and strcat into it, and free the old string; compared to buffered file writes you'll lose). It's about failing to understand how to write efficient code, not about which language you chose.

Re:Check their work or check the summary?

[gstoddart]

You know, I would argue that saying "everyone knows" is overly optimistic, bordering on naive.

Because I've seen many programmers who simply don't know, and just assume they're all equal and magic.

This was true in C 25 years ago, Java 15 years ago, and probably every other language now.

Do not underestimate the capacity of humans to be clueless and assume they know what they are doing.

My guess, audit a sufficiently large amount of code, and you'll quickly realize people simple do NOT actually know what you think everyone does.

I'm betting there's a lot of crappy code in the world which neither knows nor cares what actually happens.

My personal experience tells me there are more mediocre coders than actual good ones.

Re:Check their work or check the summary?

[Daniel Hoffmann]

Looks like someone forgot to use StringBuilder

Re:Check their work or check the summary?

[Anonymous Coward]

Please note that the authors are not in the Computer Science Dept. at either school.

Re:Check their work or check the summary?

[djbckr]

This was written by some guys that really don't know how computers work. Seriously. They have not studied algorithms nor understand how Java/Python works under the hood, nor how the operating system I/O subsystem works (specifically caching). How this wound up on /. I just don't get it. If you are doing string concatenation, at least try to do it the right way.

Re:Check their work or check the summary?

[danlip]

But they are in a loop, so what's your point?

And to be more pedantic, I don't think "+" is ever faster in Java, it gets expanded to StringBuilder at compile time. "+" is more readable and not slower if you can do it all in one statement. If spread out across control statements (if/else or loops) then use StringBuilder.

Re:Check their work or check the summary?

[MerlynEmrys67]

Here is how you make the results faster.

Compare:
1) Calculating 1MB of data and writing it to disk
vs.
2) Calulating 100K of data, writing it to disk, repeat 10 times.

If the time to write to disk is what takes most of the time, then getting the operation started early and writing to disk in parallel to calculating your data will always win. In their case - what they have done is made the in memory operation exceedingly stupid so it takes too much time. I could trivially write C code that blows their operation out of the water, unfortunately - their Java/Python code are hiding a LOT of inefficiencies in the in-memory operation. So compare their disk operation, with a cache line optimized in-memory calculation and a disk cache optimized disk write operation... It won't even be close.

Re:Check their work or check the summary?

[Anonymous Coward]

Actually, that's O(n^2) reads, writes and usage. (You can't use memory without reading or writing it, it reads and writes all the memory it uses). That makes their string concatenation O(n^2) in runtime too. It's nothing to do with the speed of memory, they're using a quadratic algorithm.

Re:Check their work or check the summary?

[Lunix Nutcase]

You know, I would argue that saying "everyone knows" is overly optimistic, bordering on naive.

As would I which is why I never used that phrase. Your quote is not my words.

Re:Check their work or check the summary?

[gstoddart]

As would I which is why I never used that phrase. Your quote is not my words.

"Except any half-decent Java developer uses Stringbuilder not + concat because everyone knows the latter is slower and causes more to be objects created"

Oh? Really? So you did not use the words "everyone knows"?

Exactly whose words were they inside of your post?

Re:Check their work or check the summary?

[Anonymous Coward]

If you do an equivalent thing you will. If you malloc a new string for every concatenation (1 byte larger than the last one), strcpy and set your new char.

Re:Check their work or check the summary?

[sanosuke001]

This is exactly why Java has a StringBuilder class.

final long startTimeBad = System.nanoTime()
String s = ""

for(int i = 0 i s += (char)Math.floor(Math.random() * 256)
}

final long endTimeBad = System.nanoTime()
System.out.println(s)
System.out.println("bad: " + (endTimeBad - startTimeBad) + " ns")


final long startTime = System.nanoTime()
final StringBuilder sb = new StringBuilder()

for(int i = 0 i sb.append((char)Math.floor(Math.random() * 256))
}

final long endTime = System.nanoTime()
System.out.println(sb.toString())
System.out.println("good: " + (endTime - startTime) + " ns")

System.out.println("diff: " + (endTimeBad - startTimeBad) / (double)(endTime - startTime))


bad: 399644443512 ns
good: 76023788 ns
diff: 5256.834130811792

Note: semicolons removed because yay slashdot comments

Re:Check their work or check the summary?

[Anonymous Coward]

+1 to comment above. Always RTFA :)

The issue they measured has got NOTHING to do with disk-vs-memory speed, and everything to do with the disadvantages of string copying on garbage-collected engines. When I worked at Google we had a related issue with a very simple algorithm O(N) that, when it was implemented in Python, ran in O(N^4) time. Ouch. Similar problem: we were making deletion edits in a large array.

Attention-getting-headline, unrelated and trivial result.

Re:Check their work or check the summary?

[sanosuke001]

Again, because of slashdot comments, I didn't realize that the internal loop code was "lost"
bad loop: s += (char)Math.floor(Math.random() * 256)
good loop: sb.append((char)Math.floor(Math.random() * 256))

Re:Check their work or check the summary?

[Anonymous Coward]

Close, but it's actually O(n^2) reads, writes and memory. You can never use more memory than you write, one of those fun little things that becomes obvious after you've taken some theory. :)

I'm actually amazed that this paper made it this far with a glaringly obvious beginner's mistake at its core. I'm very disappointed in humanity today.

Re:Check their work or check the summary?

[sanosuke001]

gd. slashdot can... ugh. both loops go to 1000000

Re:Check their work or check the summary?

[Anonymous Coward]

The problem is easy to see, in the case of in memory caching they used a String object, instead of a StringBuilder object. So every append creates a new String the size of the original + appended, copies the data into it, then sets the original String to this. The method used for the disk access is a BufferedWriter, which by its very nature is similar to StringBuilder with an initial size of 8K. If they changed to the code to use StringBuilder instead of String they probably would see time similar times between the two as StringBuilder uses an 8K buffer as well.

So really the paper is flawed, ie the premise that writing to a file directly is faster than building up that data in a memory cache. BufferedWriter does write to a memory cache behind the scenes. The author needs to ensure that disk write are happening for every call to add data, otherwise the only thing that was proven is that using a memory buffer (ie the BufferedWriter) for disk output has a significant improvement on performance.

Re:Check their work or check the summary?

[Bengie]

Yeah, the flushed after the fact

writer = new BufferedWriter( new FileWriter("test.txt"));
startTime = System.currentTimeMillis();
for (int i=0; i < numIter; i++) {
writer.write(addString);
}
writer.flush();
writer.close();

Re:Check their work or check the summary?

[Obfuscant]

In my first year of engineering I had a class in assembly but on a simplified processor simulator.

The first assembly class when I took CS was on a Cyber 6500. The assembly language was absolutely trivial to learn. The hardest part was keeping track of which ops were 15, 30, or 60 bits long so you could pack them into memory efficiently.

The next was PDP 8. Even simpler. But magical.

Re:Check their work or check the summary?

[Rakarra]

Not at all. If you wrote your C in memory string handling as stupidly as they wrote the Python and Java you will still get worse performance in C (e.g. each iteration malloc a new string and then strcpy and strcat into it, and free the old string; compared to buffered file writes you'll lose). It's about failing to understand how to write efficient code, not about which language you chose.

Yes, but we're talking new programmers here. At least in C, you're forced to have to explicitly write inefficient code. New programmers know what malloc does (if they don't, they're behind in their classes). In Java and Python, things are done for you. That can be good! It frees you from a bit of micromanagement. But again, for a new programmer, it's not apparent that they're doing something especially inefficient because the work happens invisibly. It's obvious when you have to malloc() a whole new string buffer in C every time you append to a string. It's less obvious in Java when you just append and the runtime ends up creating a new buffer on the heap for you. ASM is perhaps a bit TOO low-level and weird to start a new programmer on, but I think a full OOP language like Java or scripting language like Python might be too high-level and encourage bad habits to develop. In my CS classes, C hit a pretty good sweet spot.

Then again, you can program badly in any language, and C has its own perils.

Re:Check their work or check the summary?

[Anonymous Coward]

10 print "hello world"
20 goto 10

Re:Check their work or check the summary?

[sjames]

You've mis-understood the purpose of the paper. Read it with an open mind and you will note that they deliberately selected the most expensive string handling. It strongly suggests that they were well aware that they were stacking the deck, but doing so in a way that a programmer might carelessly fall into the trap. The intent was to educate rather than break new ground.

Re:Check their work or check the summary?

[Anonymous Coward]

I think a realistic comparison would be to handle the disk portion as:

do n 1..1000000
      if file exists delete file
      create new file
      write n bytes to file
      close file
loop

Either that, or the memory portion:

allocate 1000000 byte array
do n 1 .. 100000
      array[n] = 1
loop
write array to disk

Re:Check their work or check the summary?

[Ksevio]

The experiment is a little strange. In both cases, they're trying to write a string to a file. In one case they're doing terrible concats as you guessed, then writing to the file. In the other case, they're just writing to the file. Shockingly performing the extra step takes extra time.

They even used a class called "BufferedWriter" to write to the file stream in Java - what did they think that might be doing?

Don't worry though, they did throw a flush() in there right before the close()

Re:Check their work or check the summary?

[Anonymous Coward]

so you failed to run a unit test on your original post before hitting submit...

Re:Check their work or check the summary?

[Immerman]

Sure, if you expose enough of the implementation details it becomes obvious when you're doing something stupid

  for (int i=0; i numIter; i++) {
                    char * newString = malloc ( strlen(concatString) + strlen(addstring) + 1);
                    memcpy (...);
                    memcpy(...) ;
                    free(concatString);
                  concatString = newString;
}

Suggests strongly a number of different potential optimization routes, though most would require either multiple traversals of the source material, or a growable buffer which would greatly increase the code complexity (or does C offer such a thing these days? I've been on ++ for a long while now)

You've got to admit though, that's a lot uglier to work with for most incidental string-manipulation where performance is largely irrelevant.

Re:Check their work or check the summary?

[Anonymous Coward]

This is actually a pretty good interview problem. Anyone who writes code like that should not be hired, even for a junior position.

Seriously? You will up with no one working for you. If they show skills then hire them and teach them the rest. Programmers aren't perfect and we all make mistakes. You can't expect anyone to know all.

Re:Check their work or check the summary?

[bondsbw]

I assumed each entire string could be read or written in one operation, that's why I used O(n). But that certainly may have been a faulty assumption, considering memory/disk paging and such things that I rarely deal with at my day job.

Re:Check their work or check the summary?

[sribe]

Not at all. If you wrote your C in memory string handling as stupidly as they wrote the Python and Java you will still get worse performance in C (e.g. each iteration malloc a new string and then strcpy and strcat into it, and free the old string; compared to buffered file writes you'll lose). It's about failing to understand how to write efficient code, not about which language you chose.

It's not actually that stupid, FYI. It's a tradeoff, and the advantage of doing it this way is greatly reduced locking when you have multiple threads and the possibility of strings being shared between threads.

Of course, the paper about which this article refers, is still garbage ;-)

Re:Check their work or check the summary?

[gnasher719]

You don't even have to read the code. Reading what languages they used reveals the entire flaw. They used languages with expensive string operations when done in-memory which is the only reason why writing to a buffered cache and writing to disk is faster.

No, string operations in Java are not expensive. They are expensive if you do them stupidly.

Re:Check their work or check the summary?

[gnasher719]

That is pretty much what the article suggests. Concatenating string involves creating objects, blah blah blah...

I doubt you'd see the same "9000 times slower!" kind of results with standard C strings.

Of course you do. Assuming you allocated a big enough buffer at the start, strcat takes time proportionally to the length of the first string, because it has to search for the zero byte at the end of that string. If you want it fast, use C++ std::string, or Objective-C NSMutableString.

Re:Check their work or check the summary?

[gnasher719]

I knew a guy with a Masters in CS who loudly proclaimed optimizing was a pointless exercise.

In many cases, it is true. Not being able to optimise however is quite bad. On the other hand, in my experience when I was given code that ran too slow, it almost never was because it wasn't optimised, but because it did something stupid (like some code that downloaded n files and took O (n^3) time; worked fine with n = 10 but when I tried with n = 200 it just broke down). Changing that to O (n) isn't what I would call "optimising".

Re:Check their work or check the summary?

[hibiki_r]

It might have helped in this problem, but nowadays, even assembly language is just an abstraction: You might thing you are doing in order operations on 8086, but they are really being translated to out of order operations inside of the processor that will get the same result, but with very different performance. Branch prediction? Nah, we can run the beginning of BOTH branches, and just discard the computation we did not want, because it's actually faster. And don't get me started on the differences between what you tell a video card to do, and what it actually does.

The distance between what we write in practical, end user facing applications and what happens in the hardware is so large nowadays that it's hard to have any real control over what is going on. The best we can do is understand the performance characteristics that we see in the layer right below ours, and hope things don't change too much.

Therefore, the problem with the original paper is that it fails to really explain what we can learn from the experiment. It's not that disk is faster than RAM: That's just ludicrous. But that we really have to have some understanding of the libraries and VMs we use to get anywhere. It'd not be impossible for the JVM to realize the immutable string is being edited in a loop, that there are no references to it that could escape, and then just optimize the whole thing into a string buffer implementation that should be as good as calling the file writer: It just happens to not do said optimization for us. It's happened in Java before: Code that was seen as terrible because it was very slow is not slow anymore, and easier to read than the old school way of optimizing it.

Re:Check their work or check the summary?

[waterford0069]

If they wanted to do that, all they had to do was post this. http://www.joelonsoftware.com/...

I think they missed that the += operation is an O(n) operation, and that putting it in a loop made it an O(n^2) operation - as compared to the O(n) operation of writting to the file butter. If they hadn't missed it, then they would have come right out and said that when they were talking about using StringBuilder or StringBuffer.

Re:Check their work or check the summary?

[rnturn]

Your friend with the privileged account (I'm assuming this was running VMS, no?) might have been able to get away with using as much memory as he could. (Let's just hope he wasn't using an account with BYPASS privs enabled by default. I've encountered too many people who abused VMS boxes by setting their account up that way. They made terrible messes. Like code that can't run when accounts with less than "god" privileges are used. The problems they created were a pain -- and, sometimes, impossible -- to clean up.)

I had an intern discover that it was indeed faster to not do everything in memory. He was reading everything from a file into an array, applying some scale factor to all the elements, and then writing the entire array out to disk. It was taking forever. I had him try reading in one value at a time, apply the scale factor, and immediately write it out. Ran in a fraction of the time. Why? His account was on a system with a lot of other users. Memory quotas were enforced to avoid a single user taking over the entire system. When he read everything into memory, VMS was paging like crazy to fit his process into the smallish amount of RAM his quotas allowed and his program was spending a huge amount of time waiting for I/O to complete.

I'm guessing that I'd see the same thing happening on my Linux systems if user account ulimits weren't, by default, all set up as "unlimited".

Re:Check their work or check the summary?

[ripvlan]

Yes thank you. This is a classic mistake that many first time programmers make. Years ago somebody was comparing the speed of C++ over VBScript/IIS over Java for writing Web pages back to a browser. They too came to a similar conclusion - and also made the same mistake.

When writing to disk - the data is written once. The algorithm for in memory is not doing the same thing. It is allocating a new buffer - copying all data to said new buffer - and finally adding data to the end. If one compared the I/O of the two program executions the "in-memory" version would have many times MORE I/O.

Doing this:
    Loop N.{ x = x + newValue}
    Write(x)
Will always be slower than
      Loop N.{ Write(newValue) }

In C# and I think Java - there is an object called StringBuffer - and is intended for this kind of workload. The first thing I learned in data structures class was how to expand buffers using different algorithms and pro/con of each (heap design for instance, buddy system).

Plus - O(n) is not created equal. :-P

Re:Check their work or check the summary?

[Anonymous Coward]

Remember that sometimes memory is virtual. Your memory may very well be on a disk that's slower than the disk you're working with. Even if the disk with the paging file itself is fast, you may cause lots of head seeks.

In other words, your attempt to use more memory than is physically available may cause much more inefficient disk access patterns than if you just wrote a disk-based algorithm in the first place.

dom

Re:Check their work or check the summary?

[sjames]

They were QUITE clear in the paper that they deliberately chose the least optimal string handling. They stated it EXPLICITLY. It's not their fault you skimmed with intent to belittle.

Re:Check their work or check the summary?

[Anonymous Coward]

Only slighly. The StringBuilder with fixed size takes whooping milliseconds to do that task. Surprising, really. Who taught these guys how to code?

Re:Check their work or check the summary?

[BarbaraHudson]

Now think about the future when "everybody kan kode!" Your 16-core 4ghz cpus will choke.

Re:Check their work or check the summary?

[OverlordQ]

THATS THE ENTIRE POINT OF THIS PAPER.

It is easy to explain the results: In high-level languages such as Java and Python, a seemingly benign
statement such as concatString += addString may actually involve executing many extra cycles behind
the scenes. To concatenate two strings in a language such as C, if there is not enough space to expand
the concatString to the size it needs to be to hold the additional bytes from addString, then the
developer has to explicitly allocate new space with enough storage for the sum of the sizes of the two
strings and copy concatString to the new location, and then finally perform the concatenation. In Java
and Python strings are immutable, and any assignment will result in the creation of a new object and
possibly copy operations, hence the overhead of the string operations. The disk-only code, although
apparently writing to the disk excessively, is only triggering an actual write when operating system
buffers are full. In other words, the operating system already lessons disk access times. A developer
familiar with the language and system internals readily notices the causes of this observed behaviour,
but this behaviour may be easily missed, as indicated by examining similar cases in production code.

Re:Check their work or check the summary?

[OverlordQ]

That's their entire point.

Re:Check their work or check the summary?

[ewibble]

They basically they didn't test the same thing,

They tested concatenating 1 byte, 10 byte and 1000 byte strings in memory and disk.

In java each time you append a string you allocate an new piece of memory and copy the old string into it. When you append do it on disk it will allocate the data in blocks. The the proper way of doing this type of operation in to use a StringBuffer or StringBuilder.

The string concatenation method is order n^2 where with pre -allocation and just appending it is order n. The whole thing about order is k*n^2 will always get slower than j*n, for a big enough value of n, no matter how much bigger j is than k.

So what they are saying is don't do really stupid stuff in memory or it could be slower than doing not so stupid stuff on disk. No shit.

Oh yes then they wrote the string out to disk in the memory test as well, effectively doing the same operation as disk only method. Just to be on the safe side so your operation in memory must be slower.

Either these "researchers" are stupid or just want to make the headlines.

Re:Check their work or check the summary?

[s.petry]

Also, they are from a biology department, what do you expect?

Self sterilization and removal from the gene pool?

you asked....

probably a snark tag needed...

Re:Check their work or check the summary?

[s.petry]

No, it was the subsequent post that skipped QA.

Re:Check their work or check the summary?

[waterford0069]

Oh, I read the whole paper through. It was this line that got me.

a seemingly benign statement such as concatString += addString may actually involve executing many extra cycles behind the scenes.

I don't think they understood that += was taking a 1,000,000 cycles to execute when they got to the 1,000,000'th concatenation. I think imply by omission that the copy operation is O(1); which clearly it is not.

They do correctly identify the problem being in the data copy

The problem is caused by data copy operations in the main memory, whether in the heap or stack space. We also see that immutable strings are not inherently a problem, as evidenced by Python’s much better performance with the modified code.

But they don't identify that it's because their copy is taking longer and longer each time they do the append. Instead the leave it up to the "magic" of the append. A true O(1) algorithm for appending text (StringBuilder) would not have had the same problem; it's still doing memory copies, just FAR fewer.

It's not that there's one piranha in the river that's the problem; it's there is 1,000,000 piranha in the river. Likewise I'd rather face one piranha than one grisly-bear and 10 piranha than 10 grisly-bears; but 1 grisly-bears vs 500,000 piranha

Re:Check their work or check the summary?

[jfbilodeau]

OMG C is SOOOooOO slow compared to my l33t Java code! In the spirit of the fine paper related to this article, here's a 100% fair, unbiased comparison of both languages.
[code lang="c"]
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

int main(int argc, char** argv) {
    const char* appendString = "1";

    char* concatString = (char*)malloc(1);
    concatString[0] = 0;

    int numIter = 100000;

    clock_t startTime, endTime;

    startTime = clock();

    for (int i = 0; i < numIter; i++) {
        char* tempString = (char*)malloc(strlen(concatString) + strlen(appendString) + 1);
        strcpy(tempString, concatString);
        strcat(tempString, appendString);
        free(concatString);
        concatString = tempString;
    }

    endTime = clock();

    double totalTime = (double)(endTime - startTime) / CLOCKS_PER_SEC;
    printf("Operation took %f seconds", totalTime);
    return EXIT_SUCCESS;
}
[/code]

[code lang="java"]
public class Crap {
    public static void main(String[] args) {
        String appendString = "1";
        String concatString = "";

        int numIter = 100000;

        long startTime, endTime;

        startTime = System.currentTimeMillis();

        StringBuilder builder = new StringBuilder();

        for (int i = 0; i < numIter; i++) {
            builder.append(appendString);
        }

        concatString = builder.toString();
        endTime = System.currentTimeMillis();
        double totalTime = (double)(endTime - startTime) / 1000;

        System.out.printf("Operation took %f seconds\n", totalTime);

    }
}
[/code]

[code lang="term"]
$ cc -O3 crap.c -o crap
$ ./crap
Operation took 0.749926 seconds
$ javac Crap.java
$ java Crap
Operation took 0,009000 seconds
[/code]

Look how FATSTER JAVA is compared to C!!!!1!! You should be ashamed of using such a sloow programming language like C!

Re:Check their work or check the summary?

[ewibble]

The revelation that if you do something really stupid, its going to be slower than if you don't, not isn't exactly a new revelation is it? They could have stuck solving the traveling salesman problem in memory before writing to disk to, but that too would not have yielded any new revelations.

Big O notation has been around in Computer Science since 1976, (http://en.wikipedia.org/wiki/Big_O_notation#cite_note-knuth-11) this is hardly new research.

Re:Check their work or check the summary?

[Kleanthes]

Would be even faster if you intialized the StringBuilder with the numIter. Hard to measure, though, had to go up to 10 million 1 byte strings to actually see a difference ;-)

Re:Check their work or check the summary?

[UnknownSoldier]

> Optimizing memory is a dying skill,

It is now called Data Orientated Design.

Google+ Group
* https://plus.google.com/+Datao...

Data-Oriented Design and C++
  * https://www.youtube.com/watch?...

Typical C++ Bullshit
  * http://macton.smugmug.com/gall...

Pitfalls of Object Oriented Programming
* http://research.scee.net/files...
* http://www.slideshare.net/royc...

Re:Check their work or check the summary?

[Anonymous Coward]

It does in very few languages, afaik even in C you have to call an OS dependent method like fsync.

Re:Check their work or check the summary?

[Anonymous Coward]

Yes, but we're talking new programmers here. At least in C, you're forced to have to explicitly write inefficient code.

I cannot agree with the "forced", I have seen a lot of beginner style C code. They often go for the most obvious solution and in the case of append char to a string this meant often enough "allocate buffersize+1, copy old buffer, insert char, nul terminate, delete old buffer" put in a loop to repeat n-times.

Java generally does not hide this work either, String is an exception since the diarrhea of buffer overflow issues in C kinda forced people to include build-in string handling in any newer language.

Re:Check their work or check the summary?

[sjames]

REALLY?!? You read that and STILL don't grasp that they were aware of how non-optimal it is? REALLY?!?

Re:Check their work or check the summary?

[Nemyst]

No, what happens is that people will pre-allocate a super large memory buffer (and if their buffer is too small? whoops), or they'll completely forget to do free(), or they'll just copy code from the internet that does it for you.

Incompetence crosses language boundaries, if you think C would make them learn any faster, you're utterly kidding yourself.

Re:Check their work or check the summary?

[pjt33]

Some research into what proportion of programmers do know this kind of basic stuff would have made a much better paper.

Re:Check their work or check the summary?

[gnupun]

That flush() call is unnecessary. The writer object calls flush() as part of close()ing the stream. The writer object also flushes its buffer periodically to disk as it fills up due to the write() calls.

Re:Check their work or check the summary?

[Coryoth]

It's stupid if you're benchmarking relative efficiency -- it's not an efficient implementation (and you'll have no trouble finding explanations for why the Python and Java code they wrote, while simpler, is not efficient).

Re:Check their work or check the summary?

[waterford0069]

(Q) Did they identify the code that was the cause of the problem?

(A) Yes concatString += addString

(Q) Did they identify WHY that code that was the cause of the problem?

(A) No, they hand waved about += having to do a few more operations than StringBuilder (vs. a metric-butt load that it's doing for a million character string)

(Q) WHY did that code that was the cause of the problem?

(A) In Memory was an O(n^2) algorithm, vs. a O(n) disk algorithm
And I don't believe they understood this, or they would have explicitly explained it in their paper and/or never bothered to publish it
(Q) Is this a problem for the paper?

(A) Yes. The paper title implies that the same algorithm taking place entirely in memory (and one single large disk write) could be slower than one with lots of disk writes. They are clearly not the same algorithm when you look under the hood of string concatenation and writing to a filebuffer.

It's kind of like saying, we had a tortoise and a hare race between point A and point B, pointing out that the tortoise won the race; but neglecting to mention the hare was facing the wrong way, and ran the long way around the world. Oh, but if we switch the hare for a rabbit (which happens to be facing the right way); then the rabbit beats the tortoise - clearly the hare takes longer per stride for some reason

(Q) Are there any other problems with the paper?

(A) Yes, their lots of disk write version of the algorithm is writing to a buggered stream, and while it flushing - there is no guarantee that data has been physically written to the disk before the next iteration started. And since the PC has way more than a million bytes free on it, there's a good chance that the OS didn't have to do a physical write until long after the program finished (the disk array controller may even have a backup battery, so it could be minutes before it actually gets written to disk).


Identifying problems like this with a paper is not belittling the authors. Mocking them for publishing out of their area of expertise may be (re. Biology) or for being a potential expert (PhD. in Electrical Engineering(*)) and making what is clearly a junior coding mistake. But I'm not mocking them. I'm identifying a fundamental problem with their paper. They're grownups in academia - the should expect challenges.

* - Lord knows that he may not have any actual training in software development beyond what he needed to get through school, and may have spent more time working on the hardware aspects of computing - that was the case will all my profs that came from an EE background. PhD. and P.Eng. does not mean infallible programming expert. It means highly specialized in one are of study.

This paper has done nothing to increase the knowledge of the world, and wasted lots of people's time. It's like they published paper saying the world is round when analyzed at a sufficiently large enough scale. Be careful that you don't fly in a straight line from Washington to Japan according to a Mercator projection map because it'll take longer and you'll burn a lot more fuel. Every good pilot in the world knows that and good developers should know the problems of string concatenation (especially in loops).

Re:Check their work or check the summary?

[sjames]

You must be a glutton for punishment but I haven't the time or inclination to indulge you so:

*PLONK*

Re:Check their work or check the summary?

[Anonymous Coward]

Thank you. Finally someone gets it, instead of acting like the authors are idiots for whom the result is news.

It's like if Turing wrote a paper that used a degenerate example of a group to show that some statement in group theory was not always true, and then everyone yelled, "Turing, you idiot, nobody uses degenerate groups like that in real life".

It is not always quicker to do things in memory. Statement proved. QED.

Re:Check their work or check the summary?

[goose-incarnated]

And this is why we should not teach CS101 in Java or Python. If they'd been forced to use C this whole experiment would have turned out differently.

Not at all. If you wrote your C in memory string handling as stupidly as they wrote the Python and Java you will still get worse performance in C (e.g. each iteration malloc a new string and then strcpy and strcat into it, and free the old string; compared to buffered file writes you'll lose). It's about failing to understand how to write efficient code, not about which language you chose.

Yeah, but at least then they'd have to actually *write the inefficient code out*, thereby learning why it is inefficient. With Java and Python the novice does not know about the inefficiency because it is hidden behind a "+" operator. This is why OP said to teach in C - you have to implement the concatenation yourself and in the process you learn how not to do it.

Re:Check their work or check the summary?

[goose-incarnated]

I knew a guy with a Masters in CS who loudly proclaimed optimizing was a pointless exercise.

These days it might just be for most use-cases. For example the "research" above show this - the time consumed in 1 million inefficient string concatenations is what... less than 5 minutes? If you only perform a few hundred string concats at a time the program's user won't even notice the delay. If, like most use cases, you only concat a few strings at a time (say, a few tens) the user *certainly* won't notice. Not that I agree with such inefficiencies[1], but I *do* see the "why optimise" PoV.

There are only two rules for optimisation:
1. Don't optimise.
2. (For experts only) Don't optimise yet!

[1]One of my tasks in my first year of employment was to take a TCP stack and port to a different micro. My second task was given when the code was going through tests - I had to speed it up by a factor of two. I understand optimisation, and the important thing that I understand is that I do not have to do it much anymore!

Re:Check their work or check the summary?

[LordLimecat]

String += String

Im in a 200 level java class. We're just learning inheritance. I could have told you why thats a bad way to do things.

Do people not study what arrays are and why its expensive to continually append to them anymore?

Maybe these folks need to go back to basics.

Re:Check their work or check the summary?

[sribe]

It's stupid if you're benchmarking relative efficiency -- it's not an efficient implementation (and you'll have no trouble finding explanations for why the Python and Java code they wrote, while simpler, is not efficient).

I think we're talking at cross-purposes. When I said "not actually that stupid" I was referring to the implementation of String as immutable and highly-efficient to share cross threads, and implicitly including that there's StringBuilder for more-efficient building-up of strings. That design is not stupid.

I certainly did not mean that the benchmark or paper were "not actually that stupid". The benchmark was just ridiculously bad, and the paper utterly stupid. As some other poster said, showing that reallocating a string a million times and appending a single character each time is slower than writing a million characters into a buffer, that's literally a high-school level paper--I think I'd add that it's C-level (haha) high school work.

Re:Check their work or check the summary?

[UnderCoverPenguin]

It is not always quicker to do things in memory. Statement proved. QED.

Maybe

The disk-only code, although apparently writing to the disk excessively, is only triggering an actual write when operating system buffers are full.

The "disk-only" code is still writing to memory. If anything is proven, it's that the OS is doing its memory management better than the Java or Python run time environments.

Would be interesting to add another case to compare: Open an unnamed pipe, write to "write end" of the pipe in the loop, then read the final string from the "read end" of the pipe.

Re:Check their work or check the summary?

[Anonymous Coward]

> It is not always quicker to do things in memory.

It is if you're comparing apples and apples, which is the obvious lesson everyone is pointing to.

It's completely disingenuous to say "memory isn't always faster" when you deliberately fuck up your algorithm to prove a point. TFA should have been titled, "Naive use of memory leads to slower-than-disk performance."

Re:Check their work or check the summary?

[Trixter]

In other words, the operating system already lessons disk access times.

I guess they don't teach English at this school either.

Re:Check their work or check the summary?

[gstoddart]

Well, I'll give you my rule zero for optimizing code ... don't write shitty code relying on more layers of libraries than you can explain what is happening.

My direct experience says most of the people saying "don't optimize" are the ones who wrote the shittiest code in the first place because they simply assume all libraries are fast and efficient.

By the time you've made that shitty and slow code, it's probably too damned late to try to optimize it.

I cut my teeth writing on bare metal, and libraries which were called over and over.

If you don't start with some consideration of what is efficient, and you just do stupid things which rely too much on the library ... no amount of effort later will fix it.

Re:Check their work or check the summary?

[Anonymous Coward]

They are PREPENDING data to a string in memory and comparing that to APPENDING data to a string on disk.

Re:Check their work or check the summary?

[dataminator]

It's really sad that you are the only one who noticed this.

The paper actually makes a pretty good case that you need to be careful with operations that seem cheap but have hidden costs (object allocation), versus others that look expensive but are actually made very cheap behind the scenes (buffering). While this is of course not new, I wouldn't be surprised at all to find this in production code (as they claim), so it's good to raise awareness of the issue.

Also, I was somewhat surprised by the magnitude of the impact. I wouldn't have expected the "disk writes" to be this cheap, or the naive string concatenation to be this expensive, even though the result in general could of course be expected.

Clearly, the authors knew very well what they were doing, and designed the code to illustrate their point. They also explain very clearly what they did and why they get those results, so I really don't see why so many people claim it's deceptive. While not really novel research, I think it's very useful to have this written down so clearly and it's a great resource for new (or even some not-so-new) programmers.

This is the dumbest research I've seen this year

[MobyDisk]

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!

Chemists and Biologists

[Anonymous Coward]

They have nothing better to do with their time than benchmarking bogus string operations?

Re:Chemists and Biologists

[bobbied]

They have nothing better to do with their time than benchmarking bogus string operations?

In JAVA and Python nonetheless. Anybody who tries to draw conclusions about HARDWARE performance who uses JAVA and Python are off their rockers out of the gate. Testing the speed difference between memory and disk in Java is problematic and Python is not much better. In this case the problem really is their programming skills though. But what do you expect... Out of the three authors, only ONE isn't a biology major...

Re:Chemists and Biologists

[bluefoxlucid]

It looks like they were discussing methodology performance ("Do everything in memory! Write() is slow!"), not hardware performance.

Re:Chemists and Biologists

[Rakarra]

The problem I have with their methodology performance is that it seems like they came to a conclusion first, then wrote a test that would support that conclusion. We might roll our eyes and move on, but that's a poor way to conduct biology and chemistry research as well.

I'm actually happy this story was posted to Slashdot, because it has the side effect of illustrating a number of cautionary tales about how to do things, which I don't think the submitter or editor had in mind when approving it.

Re:Chemists and Biologists

[Immerman]

Sure, except that had they used buffered string concatenation, so that the implementation was actually remotely comparable to the buffered disk access, they would have gotten radically different results.

As it is, they've only actually showed that doing things in basically the slowest possible way in memory can be slower than writing to the disk cache (also entirely in memory, they never initiated an actual write to disk at all, only queued it)

Re:Chemists and Biologists

[Anonymous Coward]

Yes they were, but they are also oblivious as to why their experiments were fatally flawed in design and execution. All they showed was that hardware disk cache and os disk caching with a flush is fast while using poor code written in such a way as to create insane amounts of expensive ops (allocs, string copies, gc tracking, heap blows etc) is slow. In reality, the direct to disk test should be very similar to the number of ops a well designed in memory test would use as they are doing the same thing creating a string block in memory and flushing it to disk. The only difference here is the oo overhead and the fact that system librarys for disk were witten by developers while the python/java was written by windowlickers.

Obvious

[Anonymous Coward]

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. For example, using Java (on both Windows and Linux) to concatenate 1,000,000 1-byte strings in-memory and doing a single write to disk was 9,000 times slower than simply doing 1,000,000 disk writes. This applied to both Windows and Linux systems.

Probably because they're using regular Java strings, which are as slow as fsck. Something that's probably described in an intermediate Java course.

I see no mention of C in the article, which has the best means of concatenating 1000000 1-byte strings.

Re:Obvious

[amalcolm]

They also seem to be doing buffered writes, so they are not writing each byte to disk, one at a time. No JVM warmup time ... very flawed as benchmarks.

Re:Obvious

[freak0fnature]

Agreed. It doesn't even mention using StringBuffers or anything else that is designed to increase the performance of String concatenations, or even simply using a 1MB byte or char array. Not only did they fail in their programming, they failed to understand that the disk has its own memory, and their 1MB string is small enough to fit there before being physically stored on disk.

dumb test?

[Anonymous Coward]

So have they proved that writing to disk is faster than writing to memory and then writing to disk?

Re:dumb test?

[topology]

That is what they have proved. The problem is they don't even realize that this is exactly what they proved. If they had realized it (and they had any intelligence), they would be far too embarrassed about having spent so much time on this to mention it to anyone. "Look Ma, I proved 1+1 > 1"

Re:dumb test?

[Anonymous Coward]

So have they proved that writing to disk is faster than writing to memory and then writing to disk?

More like writing to a memory buffer that write to disks is faster than writing to memory (with a slow data structure) to write to a memory buffer that writes to disks.

Java and Python

[mi]

Java and Python versions of the code were written and then run on Windows and Linux systems for comparison. The total time of all writes for disk-only version was compared to total time of in-memory operations plus the disk write of the in-memory approach were then compared.

I fear, this article will be referred to for years to come as "evidence", that in-memory work is slower, while the truth is, Java and Python programs are slower, than the properly-compiled (to machine code) programs. TFA says so too:

these higher level languages are doing a lot of work behind the scenes to handle the concatenation, such as creating new objects and copying the strings in order to accommodate the extra bytes of data.

but few people will read that far down...

It is just "too easy" to write code, that will cause the useless object-creation and destruction in these "higher level" languages — and a human mind can not distinguish between a microsecond and a millisecond, so it all seems to work fine — until you need to do it a million times...

Re: Java and Python

[Anonymous Coward]

Not to mention the real world.

DO NOT DO THAT SHIT. WRITE TO MEMORY THEN WRITE IT OUT, OR WRITE ATOMICALLY.

The reason: AVs and real time backups like Carbonite. They see file modified, MUST BACKUP/SCAN NOW. Following that 1 of 2 things happens: you retry succesfully before whatever timeout, or the file is kept locked. In which case the file is corrupt, because you didn't write completely.

Re:Java and Python

[weilawei]

This is no longer happening in CPython. The naive case is specially handled to have O(n) behavior and is significantly faster than flattening a list of individual strings all at once.

"As price of RAM drops"

[mveloso]

The price of ECC ram doesn't drop for years and years.

1MB fits in cache

[Anonymous Coward]

Did they forget to flush it?

Re:1MB fits in cache

[bobbied]

Did they forget to flush it?

Of course not, it's just their program was so much of a turd that the plugged up the plumbing and the bowl overflowed before they could get the plunger. I'll bet they don't even realize that their "write to disk" likely didn't actually happen until long after the OS cached it and the program got told the write was completed.

Re:1MB fits in cache

[itzly]

They forgot to flush their research paper.

Wrong title

[Torp]

It's slower in languages with automatic memory management, or with a VM, which is no surprise.
It would be much faster than disk if you wrote the time critical parts in a language designed for, you know, speed...

Re:Wrong title

[BradleyUffner]

It's slower in languages with automatic memory management, or with a VM, which is no surprise.
It would be much faster than disk if you wrote the time critical parts in a language designed for, you know, speed...

In this case it's slower because they are not comparing apples to apples. For memory they repeatedly concatenate strings together, which reallocates the memory and copies the string every time. For the disk they allocate the whole file at once and then just stream the data. It would have been a much better test if they had allocated a memory buffer for the string and streamed the data in to it the same way as a the disk.

only useful to cs 101 students

[Anonymous Coward]

Not a good paper. Quadratic string appends are a problem, yes, but a solved one. It's why StringBuilder and [].join exist.

What the authors did

[Anonymous Coward]

The authors wrote two programs that concatenated differing amounts of bytes to strings. There greatest "speed-up" was for a case where they concatenated 1 million times a single byte to a string or wrote a single byte to disk.
As they implemented this in Java & Python, this actually meant that they did one million copy operations for the in-memory version, while the operating system batched the writes to disk together very efficiently. This is not news for anyone that knows their programming language.

Color me surprised

[Anonymous Coward]

Lousy languages produce lousy programs. Get me some C baby!

Re:Color me surprised

[amalcolm]

Nothing wrong with the languages .. lousy benchmarks ... if they had been written in C with the same skill level they would have segfaulted!

Re:Color me surprised

[greg1104]

And have a trivial exploit as a result too. It's a good thing that people who write bad Python and Java code are using those languages.

Re:Color me surprised

[Anonymous Coward]

... if they had been written in C with the same skill level they would have segfaulted!

A program can't segfault, if it can't compile.

Bad code

[Anonymous Coward]

I haven't tested the correct way myself to compare performance, but the test code used is a perfect example of how not to code Java.

They've used immusable strings for a purpose which they aren't designed. If your entire operation is to concatante values together, then it should be using a StringBuilder which is actually designed for doing this.

Bad algorithms...

[Anonymous Coward]

This just shows that bad algorithms in memory will be slower than reasonable algorithms on the file system.

In reality, both of those implementations were primarily memory backed. The implementations didn't flush the disk between each write... they only flushed the disk at the end. That means that all of the intermediate writes were actually going to memory.

So maybe the conclusion should have been "memory is faster than memory!"

bogus 'article'

[Anonymous Coward]

1. arXiv paper - not peer reviewed
2. authors never mention caching, buffers, any kind of actual technical details
3. for the Java code they use 'BufferedWriter' ... oh I wonder where their 1MB of data is going to
4. plots done in MS Office
=> the paper is complete and utter crap and would not pass muster with any reviewer on any C-rated conference or workshop

Re:bogus 'article'

[bobbied]

1. arXiv paper - not peer reviewed 2. authors never mention caching, buffers, any kind of actual technical details 3. for the Java code they use 'BufferedWriter' ... oh I wonder where their 1MB of data is going to 4. plots done in MS Office => the paper is complete and utter crap and would not pass muster with any reviewer on any C-rated conference or workshop

You forget to add that two of the three contributors are BIOLOGY majors... What are they doing writing Java code for an academic paper?

Re:bogus 'article'

[Anonymous Coward]

Something something computational biology, literal strings of DNA, etc.

a lot of questions about real-world here.

[nimbius]

Generally if you're looking to speed things up in RAM its not because youre concatenating a group of strings over and over, its because your overall read time improves dramatically as well. The study also doesnt take into account IO controller overhead...for example the overhead to write to RAM is generally mitigated in intel chips as the northbridge is merged into the processor and takes advantage of cool things like predictive instructions by the ALU. PERC raid controllers and HBA's are typically limited by the bandwidth of the bus and the clock speed of the controller on the other hand, as well as any pending rebuilds or cached data theyre committing or storing at any given time. JBOD configurations in some RAID cards also requre you to build an individual RAID for each disk, meaning the controller could have countless configurations it has to track.

an excellent example of where you want RAM to handle reads and writes is in email antispam. amavis queues get expensvie fast, despite optimized perl threading, but cutting this back to spamass-milter and keeping spamassassin in a ramdisk with its compiled ruleset there too means you can handle nearly the entire evaluation of the message without even touching the incoming queue on disk. issuing rejections at the handshake then greatly improves efficiency over having to issue bounces, which can touch up to 4 queues on disk in some cases.

Bad test or is it the headline

[ibwolf]

This is a REALLY mind boggling stupid test (or at least headline). Of course it is faster to immediately write stuff to disk as it becomes available, than to build the string in memory and then flush it to disk. Keep the IO bus full while the next write is prepared.

That doesn't change the fact that you should avoid touching the disk as much as possible, it just illustrates that if you must touch the disk, you should try to do it while the processor is busy doing other things (if possible).

Testing what

[Anonymous Coward]

I'm guessing that the underlying library caches things and is implemented more efficient than the string concatenation.

Bad code is slower than disk write caching

[mveloso]

What they're saying is if you write bad code, it performs like shit. Did someone get a PhD from this?

Re:Bad code is slower than disk write caching

[bobbied]

What they're saying is if you write bad code, it performs like shit. Did someone get a PhD from this?

Well, two biology majors did comprise 2/3rds of the contributors to this madness... I sure hope the Electrical and Computer engineer didn't get a PHD for this.. There's no way to defend this with a straight face if you ask me.

Rubbish

[Anonymous Coward]

I completely fail to see any merit in this paper at all. This whole article should be removed.

Re:Rubbish

[__Reason__]

Stop trying to suppress academic research! Papers are written by scientists, and they deserve respect!

Re:Rubbish

[topology]

Assuming your posts was not so tongue-in-cheek that you lacerated your cheek,

"Scientists" deserve respect only if they do good science. Shitty science means they are shitty scientists and deserve to be repudiated.

That's what you'd call an anti-pattern!

[cybervegan]

This:

for i in range(0, numIter):
    concatString = addString + concatString # modified: concatString = concatString + addString ...from the in-memory part of the experiment. Any Python programmer knows you don't do it this way. Strings in Python are immutable, so this re-allocates concatString every time round the loop, most likely causing multiple garbage collection cycles. It's obvious that this is not written by a Pythonista, as it's not "Pythonic" code. No wonder it's slow.

Better (maybe not the best, tho. Call me lame... )

concatList = []
for i in range( numiter ):
    concatList.insert( addString )
concatString = "".join( concatList )

Re:That's what you'd call an anti-pattern!

[cybervegan]

It's even worse - they had to rig the code badly to make their point - and the original is still in the comments!

catString = addString + concatString # modified: concatString = concatString + addString

Here, they are *prepending* catString with addString, which means that catString has to be re-allocated and re-copied every single iteration (EXPENSIVE!)

If you revert the code to the original, it runs about twice as fast as the naive straight-to-disk writer. This is due to a cPython optimization that actually extends the memory the string is stored in, and pastes the second string into it, without re-allocating and copying it, thus preventing the quadratic performance of the anti-pattern.

in-memory: String took 0.17798614502, file took 0.00357103347778
disk-only: file took 0.225710868835

When I re-wrote it using a string join, it came out like this:
in-memory: done properly 0.169091939926, file took 0.00345587730408

O(n^2) in memory slower than O(n) writes to disk

[Anonymous Coward]

News at 11...

When publishing an academic paper...

[abelenky17]

one should proof-read enough to avoid grammatical typos in the introduction:

1. Introduction
[...]
Disks, whether mechanical or SSD, have orders ***or*** magnitude higher latency and transfer times

Re:When publishing an academic paper...

[Anonymous Coward]

If you read enough papers, you see that isn't uncommon. It doesn't matter though, this paper isn't destined for being published anyway. Stupid as it is, you can tell because it's the wrong format. Journals always require the standard two column IEEE format and are usually done in LaTeX, not MS Word.

I want to mod this POST down

[AttillaTheNun]

for "idiotic premise"

String concatentation

[James Ojaste]

The paper describes using string concatenation in java to prepare the string in memory. In essence, it's comparing an O(1) operation to an O(n) operation and complaining that the latter is slower for large values of n.

Re:String concatentation

[91degrees]

It's not a complaint. It's simply an observation that perceived wisdom isn't always correct.

Re:String concatentation

[Jaime2]

The perceived wisdom is still correct as long as you don't make a grievous implementation error in one of the two things you are comparing. All that they demonstrated is "It is possible to do memory access so badly that it's slower than disk".

Impressive

[Minwee]

Unless I have misread the paper, it seems that these folks have just found experimental proof that disk writes are buffered.

"In Java and Python strings are immutable, and any assignment will result in the creation of a new object and possibly copy operations, hence the overhead of the string operations. The disk-only code, although apparently writing to the disk excessively, is only triggering an actual write when operating system buffers are full. In other words, the operating system already lessons disk access times.

I'm guessing that this investigation started with someone making a bet while their thought processes were slightly impaired.

Re:This is the dumbest research I've seen this yea

[Anonymous Coward]

But I read it on Slashdot!

Presumably, modern disk hardware caches

[Anonymous Coward]

so, really, it's not faster to worry about using the motherboard's memory, when you could be ALSO using the disk controller's memory as well.

see, that would make sense. Jumping thru hoops to avoid disk writes, which end up just being memory writes to the controller's memory, might take more time than just sending the data to the controller. THAT is totally plausible.

But, if we assume at some point the disk controller is busy. or its cache is full, because the server is doing USEFUL WORK besides this test. Then, I'm not sure I believe it.

Did the article say what kind of things they tried to avoid writing to disk? compression? I guess I'll have to actually read it, even if that's what they'll be expecting me to do...

Java Code

[Anonymous Coward]

Someone looked at the Java code used ? (PDF p8 "Appendix 1. Java code")

for (int i = 0; i numAdd; i++) {
  addString += "1";
}

Why not StringBuilder ? No one want to concatenate (lots of) strings with "+=" in Java because it is not efficient.
Maybe someone should run the test with proper Java string concatenation code and see the results, then you could tell.

Re:Java Code

[__Reason__]

"+=" does use StringBuilder - at least since Java 1.5 or so. But it still, of course, allocates a new String for every iteration of the loop.

Re:Java Code

[topology]

Which ultimately should be optimized away by a good compiler. If the string is never read in the context of the loop, leave it in the StringBuilder until the loop is exited or until the StringBuilder content is passed in a function call, then render a String from it.

Ultimately this is a failure on the part of the compiler writers to not handle a very obvious optimization. (obvious to those versed in optimizing loop code as a compiler writer should be).

Re:Java Code

[Anonymous Coward]

the problem is because += is in a loop its not doing StringBuilder.append() 1000000 times, if it is using string builder then its creating a new StringBuilder object 1000000 times and then doing a single append and then outputting it which would be significantly slower.

Re:Java Code

[Anonymous Coward]

Not only a new String but a new StringBuilder and a new char[] array on EACH iteration, making small (String and StringBuilder) and possibly large (char[]) objects proliferating in memory, requiring garbage collections. Worst possible design. Java string concatenation using StringBuilder is really useful only when you make multiple concatenations AT ONCE (a + b + c + d...)

Re:This is the dumbest research I've seen this yea

[captnjohnny1618]

Glad I wasn't the only one thinking this. I read the article and thought that I had missed something since their "task" and "conclusions" we're so trite.

String concat in java

[doctor_shim]

is an expensive in-memory operation, as it is in many other high-level languages. Unsurprising that writing a 1MB string to disk is faster.

StringBuilder

[Anonymous Coward]

Sounds confused, firstly you're not writing it out to disk, they're writing it out to the disk cache, i.e. a memory copy. They even use BufferedWriter.
Secondly they're using Strings in java, not StringBuilder, Strings do not implement concatenation quickly, StringBuilder is the way to do that.

It's all shows a very poor understanding of code. I really recommend anyone serious in becoming a programmer to LEARN MACHINE CODE or at least C so you have a decent understanding of whats going on at a lower level.

Should be: Bad String implementations are Bad

[Anonymous Coward]

What the authors did was do lots of concatenations in languages that have terrible performance for string concatenation. As it turns out, when you do something inefficient, it's slow.

I learned this after about 30 days of playing with visual basic, back in the day. It's horrible at concatenating strings. Sounds like the Java + Python implementations that they tested, are similarly bad.

So, it does prove that doing things in memory is not always faster than writing to disk. But the lesson really should be - if you find such a case, it proves the functions you are using, are horrible and should not be used when performance matters.

Distinction between in memory & disk meaningle

[chaircrusher]

One doesn't simply 'write to hard disk'. You ask the operating system to do that. The OS buffers writes and sends them to the disk in what it thinks is the most effecient blocking. And when you 'write to disk' you really 'ask disk device to write to disk (eventually)' A hard disk any more is a little computer dedicated to storing data on disk and retrieving it as quickly as possible.

Oh rly?

[Anonymous Coward]

So, they took a high level language (java,python, etc), repeatedly concatenated to a string, presumably without allocating memory in advance if thats even an option on these languages, and then wrote the result to disk. VS just appending stuff to the file on disk, and found that it's faster....... oh rly? Where do you get a job to write studies like this?

No, It's Not Always Quicker To Do Things In Memory

[hcs_$reboot]

No, It's Not Always Quicker To Do Things In Memory

The title ("No, It's Not Always Quicker To Do Things In Memory") should be modded Flamebait, Troll or similar. If it'd be possible.

With Java and Python?

[Anonymous Coward]

With Java and Python? Yikes - what a poorly done study. Do it in FORTAN or C and get the same results, and then I will believe you.

Re:This is the dumbest research I've seen this yea

[Anonymous Coward]

It's the kind of research I expect from high school kids learning to program for the first time...

Totally wrong

[Anonymous Coward]

Actually, the authors' comparison is unfair. When they do "in memory" (in the slowest setup as they recognize that appending is fastest), they add the new piece of string at the beginning of the string (which requires a copy of the old string). When they write to disk they append the new piece at the end of the file.... BIIIIP, not the same algorithm. If they had mimicked the same process on disk, the on-disk timings would just be awful.

Even with SSD, memory timings are clear, L1 cache is faster than L2, which is faster than memory, which is faster than "disk". A properly written algorithm (with the proper programming language -- indeed java or python are not the best languages for such a comparison --), will always be faster in-memory than on-disk at least as long as the data structure can stay in memory....

I bet this paper will never get published...

Stupid premise - apples and oranges

[Dr_Barnowl]

They're only examining the performance of concatenating immutable strings, versus the performance of writing to a (buffered) stream.

This is a problem that's been known about for donkey's ages. It's just that computers are so stupidly powerful it's no longer an issue that many programmers ever have to confront.

In VB6 you had to jump through hoops to do it properly, but it's such a common case in Java that the compiler will optimize repeated concatenations in a loop into using a StringBuilder instead. I presume Python has similar optimizations.

I used to just stick all the strings in an array, allocate a new string of the appropriate length, and copy them into it.

News at 11 : many less experienced programmers are ignorant of the internal workings of their chosen frameworks, because they never had to write their own implementation at a lower level.

It is easy to write slow code in an application

[cloud99]

There are SO MANY layers of caching between the application layer and the physical disk it is not possible for most applications to know that they are actually writing to disk. This is simply one example of that. Additionally, crappy application layer code runs slowly. Yes, it makes a HUGE difference how you write your code even today in how quickly it executes. High level languages simply make it easier to write code which executes slowly for no apparent reason.

Re:This is the dumbest research I've seen this yea

[c]

Pretty much my thoughts. Writing to disk is slow, but it's also semi-async operation (in that much of the time, the job is offloaded to the I/O subsystem before the write is complete), which generally means the sooner you start writing your results the sooner you'll finish, and if you start early you can do computational work while the I/O is happening rather than spinning wheels while trying to write the whole thing in one go. All they seem to have done is add a pile of latency and may even have introduced other impacts such as garbage collection or VM swap.

What the article doesnt say is telling

[Big Hairy Ian]

Basically the article doesn't give enough detail. It doesn't say whether the strings were created using the base string objects in Java/Python or using the much more efficient stringbuilder objects. The former would be horrendously slow. Also what was the base setup of the machines being tested on how much memory did they have? did their disk controllers have built in cache? What kind of disks were used.

Re:What the article doesnt say is telling

[Anonymous Coward]

It doesn't say whether the strings were created using the base string objects in Java/Python or using the much more efficient stringbuilder objects.

Want to take a wild guess? Hint: ewwwwww.

String management overhead

[Anonymous Coward]

Disk cache management is more efficient than Java and Python string management when you do a dumb thing one million times just to consume CPU cycles.
Add byte, move pointer versus Alocate new, larger string, copy contents of former strings, return old strings to pool, gargabe collect. Repeat it one million times.

Computing scientists don't understand middleware.

[Anonymous Coward]

This study is stupid.

In either case, they're still doing things in memory. The OS will set up its own buffered write to disk. That's one of many things OSs do which high-level people aren't always aware of.

By using a bigger user buffer and performing one write - memory copies go UP, cache thrashing goes UP and total memory usage goes UP, so OF COURSE IT'S SLOWER.

The disk accesses are optimized and buffered into fewer accesses behind the scenes.

This whole thing could have been skipped simply by doing a bit of research into how I/O systems and file systems work.

Their test probably didn't even touch the disk

[Anonymous Coward]

"In both cases we flush the disk file before closing it to make sure correct disk access measurements are done"

flush doesn't guarantee the OS write cache is flushed to disk, you need an fsync after that.

Million reallocations is slow, Who knew?

[Anonymous Coward]

The study's test involves concatenating some 1MB string in chunks of size n, for n in [1, 10, 1000, 1000000], then writing the string to disk. Note that for size 1000000, the entire string is made at once, and both the in-memory and to-disk methods are doing the same thing. They found that queuing many disk writes to the OS is faster than reallocating a string the same number of times in memory, then writing once. The results converge towards n=1000000, as expected. Essentially they've compared reallocations to queueing.

"[T]he concatenation code in Appendix 2, concatString = addString + concatString, places the addString contents at the beginning of the target string (vs. the end), so moving concatString is required, and a stack allocation does not help with performance. To verify this statement, we re-ordered the concatenation statement to concatString = concatString + addString, and ran the code on both Windows and Linux again. Windows’ slow concatenation results did not change, while for Linux the modified inmemory version was faster than a disk-only version, hinting at a stack allocation scheme."

So essentially, always writing to disk will be faster if you have no idea what you're doing. Obviously there are situations such as logging where repeated concatenation to disk is sensible, but this really doesn't seem to be breaking any new ground. I expect/hope that we're not about to see a huge revolution in forgoing memory in favour of disk access.

Bad applications and programming languages!

[Terje Mathisen]

What they actually compared wasn't the speed of the disks, but the speed of the language runtime and OS file IO buffering routines!

It wasn't really that surprising that concatenating java or phyton objects can be slower than letting the low-level runtime do the same task.

If they had wanted to test the disk IO speed then they would have had to add at least some fflush() calls.

It is trivial, in any language, to make your code faster than the actual disk transfer speed, but a lot harder to make it faster than a set of small block moves within (cached) RAM.

Terje

They are not using StringBuffer or StringBuilder

[RockGrumbler]

One of the first optimizations you learn when writing Java in a moderate load environment is to use StringBuffer or StringBuilder when concatenating Strings. There is probably a similar construct in Python. The test was not written from a place of experience or was purposely constructed this way to prove their pre assumed point.

Wow this was a waste of paper...

[aethelrick]

The research tells us that repeatedly concatenating strings together is a bad thing... WE ALREADY KNOW THIS!!! good grief, who taught these guys to code? The title of their paper "When In-Memory Computing is Slower than Heavy Disk Usage" implies heavy disk access where none exists. They actually go on to point out that it's the OS doing magic things that helps out. i.e. it's the OS using RAM to buffer the disk that keeps your app speedy. So erm... memory being used instead of disk then... the exact opposite of their claims

Why not have a temp ram disk card that takes old r

[Anonymous Coward]

Why not have a temp ram disk card that takes old ram say ddr1 / ddr2 / etc (runs at the slowest speed of the stick install does not need to be matched) does not need a battery and has say pci-e or sata link?

misleading

[theendlessnow]

I'd argue it's always faster to do things in memory. In the case presented here they were *not*. In both cases being compared they were writing to disk. All they did was determine the better way (for their case) to write to disk.

Comparing apples and pears!

[Anonymous Coward]

What about writing it to memory repeatedly?

This just in! Doing different things in different ways on different media will produce different results! (These guys should get a Nobel price)

Re:This is the dumbest research I've seen this yea

[Lunix Nutcase]

It's even more simple than that. Their "writes to disk" are just being stored in disk cache hence the "faster" speed. On the other hand, they do basically the most inefficient in-memory operations possible.

Buffering

[Anonymous Coward]

It's faster to use the buffering in libc or the OS than do your own shitty implementation of buffering.

I mean, I can see that inexperienced developers might make this mistake. But this isn't surprising.

Re:O(n^2) in memory slower than O(n) writes to dis

[grimmjeeper]

In other news, Pope found to actually be Catholic. The Pontiff was quoted as saying. "I always knew I was Catholic from when I was a little boy."

This just in. Massive government study shows bears do defecate in the woods. Head of the $65M (£43.6M) government funded study, Dr. Hans Schmidt, describes the study. "Ve always knew ze bears did zeir business somevere but ve were never sure vere zey did it. But now it is confirmed. Zey do zeir business in ze woods."

In other words

[Anonymous Coward]

My mantra of "If it can be done, it can be done badly in any language or any system." is proven once again.

I skimmed the paper and they're morons.

[hey!]

Here's the relevant bit:

long startTime = System.currentTimeMillis();
  for (int i=0; i

So if numIter is one million, they're generating and throwing away a million temporary objects, some of them quite large. No competent Java programmer would write a tight loop this way.

Find a subject you care about

[Anonymous Coward]

What is more interesting to me is what lead up to publishing of this masterpiece... Is it a cry for help from someone regretting their study choice? Smartasses skilled in the finer arts of trolling? Or just a magical combination of laziness, hubris and ignorance?

The experiment does not test the postulate

[QuietLagoon]

In both cases of the experiment, the disk is used, therefore the experiment cannot test whether doing something in memory is faster than doing something on disk.

.
It's a flawed experiment.

Re:This is the dumbest research I've seen this yea

[Anonymous Coward]

It's almost as if submitter "itwbennett" got this shoved thru the queue to get yet another one of his ITWorld.com posts frontpaged, despite the content itself being worthless.

Rediscovered a well known issue

[Anonymous Coward]

They have rediscovered the memory allocator copy problem.

Basically in python lets say you do this

x = x + "newstr"

So depending on how big x is will depend on how fast this operation is. You have to alloc a new buffer to hold len(x) + len("newstr"). Then memcopy it over. Then free up the old string.

That operation can be slow. If you are just appending over and over and reallocing you probably are better off with some sort of long term storage intermediate or a 'buffer' added to the end so you do not need to realloc.

So yeah depending on the string length yes a seek to the end of a file could be faster. THAT is however highly dependent on how your filesystem allocates new sectors for a file and if you are on a sector boundary.

A good way to mitigate the issue is to have some extra buffer on the end of your memory so you do not need to do the string copy. Then at that point you are doing mostly seeks with the occasional copy. This only works to a point depending on how big x ends up. So your mileage may vary.

Bad Experimental Setup

[Anonymous Coward]

There are some comments regarding Java and Python being bad languages to test this premise. That isn't a problem because Java and Python are both production languages. It doesn't matter if Python and Java are slow for these experiments simply because companies are using Python and Java for production code.

My problem is with their "benchmarks". In both Java and Python, strings are immutable. So, in order to concatenate one string to another you have to create and entirely new string by doing a deep copy. Thus, the cost of a string concatenation is the addition of the sizes of both strings, not just the second. A basic algorithms course would inform us that this is an O(n^2) algorithm. However, writing to disk sequentially does not have this cost. The file can be appended to and so the previous data does not have to be rewritten. Thus, writing directly to disk is an O(n) algorithm. With this knowledge, for any speed memory and disk, I can always find a size file that will show under these conditions that writing to a disk is faster. A better experimental setup would be to use a StringBuilder, which essentially is a mutable string. This would make the memory operation benchmark an O(n) algorithm as well and provide a much closer comparison.

However, I will add the caveat that the research is useful to some programmers. Specifically those that do not program with the underlying OS and architecture in mind. But there are many other problems than memory vs. disk writing that will show themselves if you program ignorantly.

VFS

[goarilla]

I hope thjis is not just the kernel VFS and cache doing a better job with their memory management than the researcher's code.

They went full retard.

[duhorg]

Yep, many commenters here got it right: the "study's" authors are doing teh-stupid operations "in memory". This one is so egregious, especially that the ITworld article author fell for it, that I felt it warranted its own dissection post: http://blog.duh.org/2015/03/wh...

what's going on with slashdot

[Anonymous Coward]

How could such naive stuff get slashdotted? I always thought slashdot's supposed to be for nerds.

BOMBSHELL INCOMING

[Anonymous Coward]

know your problem...

Looked at the author's names

[Anonymous Coward]

And realized why they got it wrong.

I Always Wondered

[Anonymous Coward]

I always wondered why university papers are held in such high regard. Clueless students(yes even grad students!) writing papers on subject matter that they don't understand is of questionable value to me.

I understand the value with expert supervision, when the professor is running the research, and I understand the value in peer review. But, then this paper gets cited and I start scratching my head; 'why is a clueless student's paper of any meaning to me?'

Bogus

[Anonymous Coward]

Their python results are bogus. After I fix the n^2 string aglorithm I get these results:
in-memory: String took 0.0522561073303, file took 0.000552892684937
disk-only: file took 0.184334993362

Before I get these results:
in-memory: String took 93.5676689148, file took 0.000598907470703
disk-only: file took 0.180480003357

Don't do stupid, incompetent, bone-headed things and your program won't be slow.

I changed:
for i in range(0, numIter):
        concatString = addString + concatString
To:
concatString = ''.join( addString for i in xrange( 0, numIter ) )

Of course you can do better:
concatString = addString * numIter
Produces:
in-memory: String took 0.000266075134277, file took 0.000687122344971
disk-only: file took 0.194098949432

Stupid is as stupid publishes....

[TiggertheMad]

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.

Re:Stupid is as stupid publishes....

[Bengie]

They should follow best practices and use StringBuilder and rerun their tests.

Re:Stupid is as stupid publishes....

[Dr_Barnowl]

It's such a common case that Java will usually optimize looped string concat into a StringBuilder now. I imagine Python does the same thing.

The performance probably still sucks because the buffer needs re-allocating periodically (in StringBuilder, it doubles each time), but not as much as it would in VB6 which has no such cleverness in it's immutable string type. There's also all the garbage collection overhead for all those discarded byte arrays.

Would be more interested to see a benchmark if they declared the StringBuilder with a buffer of the size they expected to use.

Re:Stupid is as stupid publishes....

[Anonymous Coward]

The paper should be titled async faster than sync io operations if the measure is response time. When you write data in a posix OS, you have to receive an acknowledge that it wrote. In memory there's no cache. On disk there's a cache (the commit queue) that can ACK the data much faster than actually write it.

Re:Stupid is as stupid publishes....

[Anonymous Coward]

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.

That depends entirely on the language they used. If it's Java or .NET, sure, strings are immutable which means you end up copying that string all over the place. If it's C, they could use malloc/realloc, or better yet, just allocate the entire million bytes in advance, and append bytes within their fixed-size block of memory. That's what any sane programmer would do if they knew the exact size of the data they were working with, or even if they didn't but they needed a buffer and the data happened to fit comfortably within it.

This is why scientists aren't programmers and why nobody in the real world takes academic papers as serious, unqualified gospel. Either the list of asinine assumptions is a mile long, or there's some ignorance of practicality that makes the entire premise of the paper laughable. I'm not saying there isn't a place for this type of research, but the press releases need to be severely curbed.

Re:Stupid is as stupid publishes....

[Mark of the North]

I've actually worked with one of the authors. Nice guy. The analysis in the paper is so shallow that my guess is that it was primarily done by a graduate student, probably as part of a course but never successfully peer reviewed. I sure hope it wasn't accepted anywhere.

Re:Stupid is as stupid publishes....

[msobkow]

Java's "StringBuffer" object can deal with concatenating source code fragments to produce 6 million lines of code in under 8 minutes and write it to a 7200rpm HDD on Linux. Java handles string concatenation quite efficiently if you're using the proper data objects instead of naively doing actual string concatenations that require much more buffer re-allocation than simply extending the end point of a buffer that is periodically reallocated with n extra bytes each time. And that's only on a creaky old P4 3.8GHz with DDR2-800 memory.

I call "bullshit" on the paper.

Re:Stupid is as stupid publishes....

[Dastardly]

It is even worse than that. They are using a BufferedWriter for the so called writing to disk portion. So, they are actually comparing the worst possible way to append a String in memory to appending bytes to a bytes buffer and periodically writing that to disk. So, basically comparing two different in memory string appending techniques? When you bring the OS into play it is even less likely to actually show anything having to do with the disk because the OS will write asynchronously.

My grade: F- and they should be mocked mercilessly until the paper is retracted for being idiotic.

Re:Stupid is as stupid publishes....

[ndykman]

I strongly encourage people to email the authors and clue them in. Seriously, this makes me angry. If CS doesn't already have a reputation for being completely academic and out of touch. Things like this, no wonder people think you can learn to code in 10 weeks.

Re:Stupid is as stupid publishes....

[PIBM]

They chose to use a 2006 version of java so that it would not be optimized away perhaps ? It looks like a troll article to me.

Re:Stupid is as stupid publishes....

[BarbaraHudson]

The other issue is that the OS and disk cache will buffer those one-byte writes, whereas they went out of the way to use the worst code possible for in-memory operations. Appending 1 byte a million times creates and destroys 1 million instances. If they had just created an array and written each byte at the appropriate offset, there's only one instance. A lot faster.

Re:Stupid is as stupid publishes....

[Darinbob]

Trouble is, people are taught things but they don't actually learn. Instead they take what they are taught as "the truth" and never actually thing about what's going on. Rules of thumb become dogma.

This isn't just from newer schools who only teach job training courses for high level scripting languages, this effect also happened even when schools taught from the low level chip design all the way up through theory.

Re:Stupid is as stupid publishes....

[Mark of the North]

None of the authors have a CS background. Two are products of Electrical Engineering, one of which is a professor (whom I worked with at one point). The other is from the Department of Biological and Chemical Engineering.

Re:Computing scientists don't understand middlewar

[Anonymous Coward]

None of the authors are computing scientists. Look at the paper they published. One is studying biology, one is studying either electrical or computer engineering and the third is studying either chemistry or biology.

True for certain database operations

[avandesande]

In SQL server, large memory table objects can be slower to join with or access than temp tables due to lack of indexing. I am sure you could find other cases where memory might perform worse than file access.

What morons

[m.dillon]

What morons. Sorry, but they are. They are writing to a file through the operating system which means that it is being spooled out to disk asynchronously, so obviously piecemeal writes are going to be faster because they will run concurrently with the string generation algorithm. Plus their 'writes' are probably being buffered in ram anyway.

Writes to files generally do not stall programs. These people are morons.

-Matt

JAVA FTW

[Anonymous Coward]

Another shining example, of why anything that has to do with performance, should never, ever, be coded in Java. This would be akin to writing a numerical algorithm using floats instead of doubles or even single precision, or coding an operating system in java, it would take weeks just to boot!

Now if they really wanted speed and performance, they should have run the code on a java interpreter, running on a java interpreter written in java, running on a java interpreter ... ad infinium, because recursion makes things faster, and java is faster than C, everyone knows what!

Re:JAVA FTW

[Anonymous Coward]

For some tasks java is faster than C. The tests I did myself for fast Fourier transform - java JIT is faster in about 1.5 times.
Java JIT optimise code on runtime, taking into account actual function argument values. Not every problem will be faster, but small size (up to 100) of FFT or solving linear system is really faster in java than in C or fortran. A problem with larger dimension - make this difference it speed disappear. Try it yourself. I am not saying, that java is always faster, I am saying that java is often faster.

If you read section 2.3...

[Anonymous Coward]

...you would see that the authors are aware of every criticism that has been stated here thus far.

python and java

[Spazmania]

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.

Re:python and java

[Just Some Guy]

Python's string library isn't remotely what I'd call "overweight", but its strings are immutable. Some algorithms that are quick in other languages are slow in Python, and some operations that are risky in other languages (like using strings for hash keys) are trivial (and threadsafe) in Python. But regardless of the language involved, it's always a good idea to have a bare minimum of knowledge about it before you do something completely stupid.

Does Slashdot have editors?

[Afty0r]

Can we reject things like this please?

Or possibly have a "-1 written by an idiot" mod option, and enough of them removes it from the front page?

Painful dribble- but expect a LOT more of this

[Anonymous Coward]

Now that having a vagina is a legal NECESSITY for any coder receiving funding from a US state facility (or from a major politically correct IT company), you can expect an awful lot more GARBAGE flooding the annals of Computer Science.

I am reminded of the sickening NASA press conference, that announced a totally new form of life on Earth. A BRAIN-DEAD female, employed by NASA purely because she was female, had been given a team of mostly male science slaves, to pursue her NONSENSE theory that because she remembered the stupid simplification of the Periodic Table during her High School years (when teachers over-state the similarity of elements in the same 'group') DNA variants must exist in nature where one element of usual DNA would be replaced with ANOTHER element from the same group. This is a kin to saying that because a water-wheel is technically related to a gear, you might expect to find water-wheels within a mechanical watch. The 'science' she had used to 'prove' her hypothesis was the most humiliatingly awful pile of garbage, but her male colleagues had been forced by the upper echelons of NASA to claim her a 'genius'.

When ability is replaced by political correctness, and an anti-nerd program is implemented in most US schools and universities, standards don't just fall through the floor, but one enters an 'Emperor's New Clothes' phase in the USA, where anyone who wishes for any form of success MUST lavish praise on the ravings of cretins that the politically correct establishment is currently presenting as figure-heads.

Now this isn't an anti-female point. To the contrary, because of the bias towards males in engineering, the VAST majority of incompetents I have encountered have been males- some with significant power and/or influence. However, this is common in any system (scum rises) - and is different from a system FORCED to bias itself to selling one type of Human over another.

Bill Gates and Rupert Murdoch's 'Common Core' (don't forget, these two monsters- supposedly from either end of the political spectrum- are actually CLOSE friends- and work together on the 'new' education projects in the USA, like the now at the NSA 'inBloom' obscenity) initiative is already dumbing-down education in the USA, and placing maximum hurt on the male Beta experience in technical subjects- especially maths. Put simply, Common Core is designed to ELIMINATE the influence of natural Alphas in the classroom, and place 100% of the intellectual authority in the hands of teachers - adults that frequently have such poor skills in their 'subject', they actually fall BELOW the Beta designation. The underlying idea is that non-alpha kids will have too little innate confidence in their own skills at that age to challenge the system, and that the alphas will 'withdraw' and simply succeed with ex-classroom activity.

PS as for the hopeless article promoted by Dice (no accident there), the 1MB data set hits the common L2 cache limit by no co-incidence. The concept of 'memory' on a modern computer is a complex chain of 'L' caches, where the RAM of the system is actually L4 cache, the SSD drive should be used as L5 (but rarely is), which would make the hard-drive L6. Normally, under a properly designed memory-management system, one wouldn't be explicitly writing anything to the hard-drive UNLESS it was to create or alter a permanent HARD-file.

The speed of a modern CPU cluster (4+ cores in a modern work-horse PC) is so much faster than the data rate to a HD physical platter (as opposed to the RAM cache of the HD), it isn't funny. But usually when doing explicit HD writes, on accepts on that thread that the thread is going to be limited to the speed of communication to the HD. That thread, of course, will not even dominate the run-time of its own core since each IO stall will allow another thread to take its place until the HD has finished its current DMA activity.

The computer is NOT a black box, and coders who treat it as such, because their knowledge comes from politically correct teaching, havin

HOT BREAKING NEWS!

[Alsee]

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.

-

But file writes are buffered!

[ggraham412]

So in a nutshell, they compared the cost of the most inefficient method of in-memory string concatenation versus an efficient method of in-memory string concatenation: the memory in the latter case being a buffered file writer. Lololol!!!

Re:They are not using StringBuffer or StringBuilde

[Anonymous Coward]

And one of the first things you learn if you bother to learn about how your compiler works is that the java "+" operator on strings is replaced with stringbuilder under the hood in any remotely modern version of the language.

Re:This is the dumbest research I've seen this yea

[Jaime2]

It's dumber than that. They didn't even do it right in Java. There is a note near the end of the paper that says "However, using a mutable data type such as StringBuilder or StringBuffer dramatically improved the results". They didn't present the numbers, but what they really meant was "The performance problems we saw were entirely due to our not using StringBuilder or StringBuffer, this paper shows no meaningful difference in performance between memory-then-disk and disk-only access once the algorithm is fixed."

This is RESEARCH?

[orlanz]

Ok, I read all the other "This is stupid" comments and my jaw kept dropping. I actually felt this was an April fools thing or something similar and that we were all missing something somewhere (and please let me know if I am... I REALLY need to know). I HAD to read the article and underlying paper, cause I just couldn't believe the absolute asinine stupidity of the test, let alone that it was being presented as research, or that the test itself was so flawed! So after all that, had to post. Summary for others, adding my voice to the crowd.

----------------
Assumption: Software Developers avoid disk access cause they believe doing it in memory is faster. This is put in context of BI and bigdata.

Testing: Create a program representing a common task that can be tested where one uses memory and the other uses diskspace.
Memory Test:
1) Create a string in memory.
2) Add it multiple times into another string
3) Write second string onto Disk
4) Flush writes

Disk Test:
1) Create a string in memory
2) Write it multiple times to Disk
3) Flush writes

Create code in Python and Java.

Conclusion: Memory Test is so much slower than Disk Test! Additionally, the languages used have certain quirks to make it worse. Optimization helped a little but only on Linux. Therefore, programmers should reassess and understand their OS and programming languages before assuming this belief which is not true.
---------------

Assumption & Testing idea... very good. I would have loved to know the unknown scenarios where this assumption should be questioned. Especially in the world of click&drag programming for workflows, ETLs, and report writing.

But from there... its all BS and stupidity. Basically the test tests if replicating the hard drive driver in memory and then using the driver to write to disk is faster than just using the driver to write to disk. Are you bloody serious?!?! That's like testing if 2+2 is greater than 2+0. And that is before we start looking at using Java and Python which do a ton of work in terms of memory management and build all types of stuff around data types. Before the fact that they wrote the Python code WRONG (that's the slow way of doing string or listing concat). So they picked languages that write in memory O(n) extra times for the same data.

This test would have come to the same conclusions in C, C++, or Assembly! But the folks wouldn't have been able to write code to see the micro second time differences.

So lets set the record straight. NO developer out there goes out of their way to just write to a memory file if its simply going to flush to disk. Its not worth the extra lines of code, nor the lost CPU cycles in reading them. Especially since most operating systems do this already at multiple points along the data chain at the very low hardware & driver levels! If we have developers like this, we have a ton of bigger problems in software development than this little thing that will be solved by money.

To test this belief properly, give me a scenario where you reuse the written to disk/memory stuff, transform it, and then write to disk. See which one is slower. If its written properly, you will see that the underlying hardware systems will actually store stuff in cache or memory for you to help you speed it up! If you find proper scenarios where the memory part is slower, please let us know cause that is actually adding to the IT body of knowledge.

God, as this was BigData related, I was hoping at least something along the lines of "In DB data processing and extract vs extract and client side processing". Give me the points along a curve where one is better/worse than the other. THAT would have been interesting.

Depends on the situation

[MagickalMyst]

"...alternative ways to create a 1MB string and write it to disk"

This is not surprising if the goal is to write something to the disk.

But what if you were to write something to the screen instead?

Would it be any faster to create a 1MB string on the disk and then display it on the screen? Probably not.

Not to mention that writing to the screen really is writing to memory; as opposed to a disk which is a slower, physical medium.

So really, like anything it depends on what you are trying to do.

It may not always be quicker to do things in memory, but it usually is.

Strange

[nospam007]

Can't be.
I just ran a dBASE III test with my first harddisk I ever got, a full height 20MB Seagate and memory always won.

Re:This is the dumbest research I've seen this yea

[falzer]

>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!

Agreed with you on the uselessness of their research, but that is most definitely one important and common use of memory: buffer caches used by the operating system.

Effectively, they unintentionally tested the speed of the OS to concatenate strings vs Java or Python. The researchers are wrong right out of the gate: they say "Heavy Disk Usage" in their research headline, but at no point did they actually test disk performance, everything they did is being handled by the OS buffer cache.

All the researchers have shown is that string concatenation operations in Java and Python are atrociously slow. The java example used the naive form a=a+b; to concatenate strings, which is one of the slowest ways to do it in Java if you are doing repeated concatenations to a string.

If, in their tests, they had also done a string concatenation in C by allocating a buffer and appending to it using a pointer (not strcat) the speed difference doing that vs. 1 million write calls would have been negligible.

Also, if they sync'd after each of a million 1-byte writes to test how slow "Heavy Disk Usage" is compared to a single write of a million bytes, they wouldn't have bothered finishing this paper at all because it's so damn obvious that memory is faster.

We're all doing it wrong!

[jetkust]

Maybe we should store our files in memory and load them into the harddrive to do calculations.

Re:We're all doing it wrong!

[hcs_$reboot]

Maybe we should store our files in memory and load them into the harddrive to do calculations.

And the swap would be also in memory... What a fast swap we would get!

Re:This is the dumbest research I've seen this yea

[MerlynEmrys67]

What do you expect... There is only one person that MIGHT have a computer background on the paper... This is pure academic fluff, compare an in-memory database with a spinning rust based database and see how many operations you can get out of each one performing the same operation.

No way, unless extreme incompetence is employed

[gweihir]

Unless you really mess up your in-memory variant, there is no way in this universe that disk access can be faster. Here is a simple thought-experiment that shows this: Just use an in-memory array as storage vs. the disk. The array must be faster as RAM has orders of magnitude better bandwidth and latency as even the fastest SSDs, and it has far, far smaller block-sizes in addition.

Of course, if your in-memory data storage is so badly organized that the OS in-memory (!) buffer-cache does a better job, you may think that you observe the disk being faster than your RAM.

Looking at the paper header, the authors are all from a biology-department, so the suspicion that they are clueless of how to write things efficiently is really not far-fetched. I will not read the paper, it is likely a waste of time.

Re:No way, unless extreme incompetence is employed

[viperidaenz]

Don't forget that to write to disk, you must store the data in memory first.

Re:No way, unless extreme incompetence is employed

[gweihir]

Indeed.

Re:Computing scientists don't understand middlewar

[Anonymous Coward]

I guess that explains why they're treating computing as observational science which it is not. This still doesn't explain why anyone approved this study to begin with when they could just ask someone who is knowledgeable with computer OS internals... or, god forbid, do some preliminary research on the topic.

Not realistic Either

[Anonymous Coward]

Try 1 million writes with 5000 files. Their example doesn't apply when scaling.

Wow who would have thunk it!?

[nedlohs]

Writing lots of small strings to disk one by one, is faster than building an in memory string up from those small strings one by one - reallocating a larger chunk of memory and copying the entire current string on each little step.

It's almost like memory allocation and copying data over and over might slow things down a bit over simply not doing that at all.

Honestly the paper is completely retarded. Only a moron would not expect that result.

Caching explains much of the difference

[davidwr]

The results were poisoned by the presence of various caches affecting disk I/O and for that matter memory I/O. On some modern systems, either the disk lies to the computer or the OS lies to the application and the application thinks the data is actually stored on the bare metal before it is really stored (the data may or may not be stored in a "safe" place like a non-volatile cache - the point is that a small write operation returns "success" very quickly, much faster than if it had to wait for the bits to be written to the platter).

The only thing they can really say is "on this hardware, using this operating system, under this workload, these are the results of our experiments."

I'm not saying their results aren't useful - they are. Instead of presenting this as "memory writes are faster than disk writes" they should say "in some or many modern systems, under some circumstances, it may be more efficient for programs or operating systems to write to external storage devices in small bits rather than going to extra work to minimize the number of writes to such devices. Don't assume that what was true about the performance of an application calling an operating system to perform a disk-write operation or of an operating system asking a hard drive to perform a disk-write operation is the same now as it was a decade or two ago."

Just don't call them "disk writes." Call them what they are - "requests by the application or the OS to the OS or hardware to perform a disk write."

the correct java way

[Anonymous Coward]

Here

        public static void main(String[] args) {
                final long time = new Date().getTime();

                StringBuilder sb=new StringBuilder();
                for(int i=0;i<10000000;i++)
                        sb.append(" ");
                System.out.println(new Date().getTime()-time);
        }

The result is 101ms on my JRebel instrumentated JVM

I hope he fail, he is a disgrace on Canada

Re:the correct java way

[Anonymous Coward]

to get twice faster use a ' ' instead " "

Skepticism is a duty.

[Anonymous Coward]

It's nice that competent people are shedding light on things like string copying, real disk I/O versus OS-mediated buffered one.

This is great even if the paper turns out to be flawed.

That notwithstanding, let me tell about a personal experience, take it FWIW: I made a course where I opted for results of command output to screen; my less computer-savvy friends left the default of data output to disk.

To my surprise, output to screen never happened (other things were being displayed very well, thank you); just by using the command for disk file output, results were immediate. Being in a course where following the subject was mandatory, I left the question aside for further reflection.

In real-life (and that's what the paper is about), things happen and it's great to better understand how 2015 hardware could be surpassed by a 15-year old one because better software choices were made.

(I'm looking at you, registry.)

Windows in RAM

[Anonymous Coward]

I ran Windows in RAM it was much faster.

Is this an onion article?

[Anonymous Coward]

Non peer-reviewed research should be published in the onion, at least this way we all know it's a joke, and news sites would stop posting this garbage as real research. The summary of this paper is you can write terrible code that makes in-memory look worse than disk because you don't really write to disk, the os does, and you don't know how to actually measure in-memory vs disk access.

makes perfect sense

[Anonymous Coward]

Did you actually read the paper? It makes a lot of sense, it just isn't that surprising if one understands the reasons.
The in-memory-operation (string concat) causes a lot of memory-copying. The disk-writing doesn't, because the system isn't really writing out stuff for each such request, but is buffering the data in a way that is more efficient than the copying of immutable, fixed length strings.
Their message isn't "wow, disks are faster than memory after all!". It's "don't teach developers to blindly favor in-memory over disk in all cases, teach them how stuff works on all levels".

writing to disk repeatedly?

[Anonymous Coward]

sounds like a bit torrent client with a small disk cache. I once ran Utorrent with a 1 MB cache or perhaps no cache at all. The hard drive light blinked continuously and the motor sound didn't stop. After I enabled the cache, the hard drive did not make much noise. Computer did seem to run slower when the cache was small or disabled too. Or maybe I was imagining things.

Don't over-optimize

[Immerman]

Correction: Dumb concatenation is for situations where clarity and convenience are more important than performance. That is to say, most of your code. If you're using a buffered string building system to perform a simple concatenation of file name components before opening the file to begin the real work, then you're creating maintenance headaches for an irrelevant performance boost. In an inner loop dedicated to string manipulation though...

One of the most important aspects of programming is knowing how to choose the right tool for the job - typically 80-90% of your codebase is executed so infrequently that even abysmal performance won't be noticeable to the user, and optimizing that code will actually be counter-productive due to the time and maintenance overhead it imposes. Moreover, most programmers (and especially the inexperienced) are quite poor at recognizing which parts of their code are actually performance critical. Recognizing that, it may often make sense to default to doing things the simple, slow, way and only worry about optimization after performance analysis has highlighted the bottlenecks. Personally I'll often write the expected hotspots with some basic "low-cost" optimizations (like StringBuilder) and an eye towards making future optimization simple (expected optimizations should never require an architecture overhaul, and maybe it's worth passing in certain data that will be necessary for future optimization of a heavily used function, just to avoid having to re-write a million function calls if/when it comes time to optimize it), but primarily focus on correctness. Then, after everything is working correctly, and performance analysis has shown me which bits of code are actually causing issues (including the bits I never would have suspected), then I go back and break out the heavy guns. I've gotten burned too many times over-optimizing the wrong things and generating headaches down the road to make a habit out of it anymore. Unless it's something fun to implement of course...

These aren't the droids you're looking for.

[Anonymous Coward]

... Move along.

This proves only that...

[Anonymous Coward]

The author of the paper knows nothing about how strings work in Java or Python. Every time the string is concatenated in a loop, the interpreter creates a brand new string. The "in-memory" code isn't doing the same thing as the "on-disk" code.

What an Idiotic Paper

[rrr00bb5454]

Holding the string in memory serves no purpose at all if you are just appending to it. Frankly, this += of strings issue is the most common "Smart but Green Self-Taught" versus "Computer Sci grad" problem you will see with new hires. Appending strings can be O(n^2) when the strings are immutable, and it applies to most high level environments. Even Metasploit had this issue at one point, and it was written by some very smart people. So everybody learns to keep appending to a list, and then flatten it to a string at the end. But this tie in with disk just makes the paper totally dumb. If you won't be reading the queue of string chunks, just flush them to disk immediately so that the code runs in constant space - relieving the memory allocator.

Repeated Java string concatenation is O(n^2)!

[FizzyP]

Concatenating strings one character at a time in Java has QUADRATIC performance (i.e. O(n^2)). If they used the StringBuilder class instead I bet most of their bottlenecks would disappeared. With that class it should be amortized O(n).

Re:Repeated Java string concatenation is O(n^2)!

[FizzyP]

Correction StringBuilder performance would be amortized O(n log n)

In other news...

[Anonymous Coward]

Using a system with no congestion to write a small amount of data (that fits entirely in said cache) to disk cache before it is flushed in one flush is fast, and constructing code to perform obscene numbers of ops on modern operating systems using highly oo languages perform slower than not doing so. Gun -> Head = blown.

 

Your code sucks

[viperidaenz]

String concatString = "";
  for (int i=0; i numIter; i++) {
  concatString += addString;
  }

That's going to create 1,000,000 StringBuilder objects, use them to append a single String each, and allocate 1,000,000 new String objects as well

StringBuilder builder = new StringBuilder(
  for (int i = 0; i numIter; i++) {
  builder.append(addString);
  }
String concatString = builder.toString();

I bet $1,000,0000 that code is faster.

tl;dr; Researchers who don't know who Java works suck at writing Java benchmarks.
String a = b + c;
gets translated by the compiler to something like:
String a = new StringBuilder(a).append(b).toString();

It's creating a new StringBuilder object, its member variables including a char array, it copies the String passed in to the constructor. Append is probably also expanding the array, which means creating a new array and copying the old one to the new one, then copying the data from b to the end of the new array.
toString then creates a new String object, copying the data again.

If you write shit code, you get shit performance.

Re:Your code sucks

[t-wata]

Also he uses BufferedWriter for "write to disk" test. If he uses FileWriter and your code, then he would get opposite results.

Re:Your code sucks

[viperidaenz]

Depends. That may only lower the overhead associated with copying the data from the user process over to the kernel. The kernel may still buffer the writes to disk.

Bad algorithms

[Anonymous Coward]

Breaking News: Badly written code is worse than well written code!

This illustrates why PhD's shouldn't be in busines

[Tony Isaac]

Of course, there are exceptions. But many PhD's I've known make lousy programmers, in terms of producing good software.

I've come to think that the skills needed to be a good post-graduate student are different from the skills needed to be a good professional developer.

Professional developers know (or should know) how to optimize code, when necessary. All else being equal, optimized code will ALWAYS be faster in memory than on disk. The two examples in this research are NOT equal. A more equal test would be to output to a memory stream, vs. a file stream. I'll bet the results would be quite different.

lol

[Anonymous Coward]

Drool ops resulting from code written by windowlickers is slower than os/system library for disk access written by developers; especially when the data fits completely in os and disk hardware cache.

Yes, yes it is

[Anonymous Coward]

If you do it correctly, and use the right tools for the right job, on-board memory will ALWAYS be faster than physical disk (and even SSD's)

How about a string of 9's?

[jdavidb]

How long to create a string of 9's?

This is why love C

[aglider]

In C you always know where the pitfall is. Or at least you have chances to really know.

Re:This is why love C

[hcs_$reboot]

A bad algorithm in C may perform worse than a good algo in Perl. Fortunately the C programmers do usually know what they're doing.

Send it to Linus Torvalds!

[Paul Mallako]

Could someone please send this paper to Linus Torvalds? I'd like to hear his opinion on this paper. =)

Re:Send it to Linus Torvalds!

[Anonymous Coward]

Never mind that, what does Bennett Haselton think?

Stupid is

[Anonymous Coward]

as stupid does

Cherry-picked example

[jtara]

See subject.

Re:This is the dumbest research I've seen this yea

[c]

Their "writes to disk" are just being stored in disk cache hence the "faster" speed.

According TFA, they actually do an explicit sync to disk at the end of the writes. So it's not purely writing into cache.

Free performance boost

[StikyPad]

I was about to upgrade my hardware, but instead I just pulled all my DIMMs and I'm only using virtual memory now. My computer is like a million times faster, and I think it even got rid of some viruses that were hiding in memory.

Now if I could just figure out why that goddamned System Idle Process is using so much CPU time!!!!!

So, this is how bad research can get...

[ndykman]

Awful. So, in a language with immutable strings, building a string like so:

for (int i = 0; i < 1000000; i++) { str += "1"; }

is really slow, but if you use a file buffer like so:

for (int i =0; i < 1000000; i++) { fileBuffer.write("1"); }

it's much faster. Wow. No kidding. Also, note, they don't flush until the end. This is laughable. No wonder CS programs are under attack if this is the kind of thing that people think they can publish.

Re:So, this is how bad research can get...

[SLOGEN]

They seem to be from a biology department, not CS :)

Re:So, this is how bad research can get...

[ndykman]

Well, one author was listed as being from a Electrical and Computing Engineering department, and I would expect he or his peers would be able to see how pointless this is.

Stringbuilder? Perhaps.....

[TiggertheMad]

Many people are suggesting using string builder, as a easy fix...If you think about this problem, that doesn't solve it as you approach infinite operations, it just pushes the cost crossover point way out (possibly beyond the limits of existing hardware, so it might be practically moot). Since they are doing silly comparisons like this, I would suggest just writing a linked list to store each byte as a counter example that will provide more of an apples to apples comparison. Adding an element to an linked list will have a fixed cost, just like appending a byte to disk will, so after infinite operations, you could demonstrate that memory operations are always going to be faster performing similar tasks when the IO time of memory is faster than disk IO.

Re:Stringbuilder? Perhaps.....

[Anonymous Coward]

that doesn't solve it as you approach infinite operations, it just pushes the cost crossover point way out (possibly beyond the limits of existing hardware, so it might be practically moot)

Afaik the internal buffer of a StringBuilder doubles each time it resizes, something to do with amortized O(n) which is faster than O(n2).

Newsflash: Buffering works!

[ggraham412]

That's what buffered files are supposed to do: make slow disk writes appear as if they are as performant as memory writes.

Apples to Oranges

[Anonymous Coward]

Many problems here:

FIRST:

This is not even remotely comparing apples to apples. In the first case they continually concatenate a string. i.e.

strCat = ""
for loop for some time:
        strCat += "1";

In the second case they continually write "1" out to a file.

One problem is that they are claiming to test whether doing something in memory is faster/slower than _doing the same thing_ while reading/writing to disk. But they haven't accomplished this. In the first case, they are ending up with an object of type string that resides in memory, in the second case they are ending up with a file on the disk, but do not have the string anywhere in memory. So to really compare, they either need to write strCat out to disk, which is _obviously_ slower than the second method (would anyone have claimed otherwise), or they need to read back in the file at the end which may or may not have changed the outcome.

SECOND

Any Java programmer knows that the first option is slow and is doing a lot of unnecessary object creation. When programmers say its better to do stuff in memory than writing it out to disk they don't mean, use whatever algorithm you want and no matter what it will be faster if you do it in memory than any algorithm you might choose for writing to disk. Would have been slightly more impressed had they used a StringBuffer, but I doubt that will get the same results, and that is Java 101, so what the heck do they think they have discovered?

Never written a line of assembly in their lives

[Anonymous Coward]

This is the kind of stupidity you can expect from a Java-based education.
At least one basic assembly class should be mandatory to call yourself a computer scientist.

Facepalm

[lorinc]

This kind of useless paper is exactly why idiots should not be allowed in computer science. They even give the explanation in the paper and still draw to bad conclusion. To me, it should be renamed "Bad programming habit performs worse than very bad performing habit in the absence of knowledge about the tool used".

Re:This is the dumbest research I've seen this yea

[Xyrus]

Agreed. This has got to be some sort of April Fools joke. There's no way this is a serious piece of research, much less actually pass a peer review process. Even a junior level programmer could tell you how stupid this paper is.

Some tips for the authors of this travesty:

1. Learn how computers work.
2. Learn how operating systems work.
3. Learn how programming languages work, especially ones that are interpreted or VM/CLR based.
4. Learn2code.

This "research", if it actually is research, should be nominated for an Ignoble Award. This would deserve an F even in an intro to programming course.

I think I'll go write a paper on how having lots of polygons in a 3D model will slow rendering down. I should get two Ph.Ds for that work.

Re:No, It's Not Always Quicker To Do Things In Mem

[Anonymous Coward]

From the title, I thought they were going to be using CPU registers or something.... then I read the summary and was like WHAT? Got to be a mistake there. Then I read the comments and it all made sense. Not going to bother reading the article.

Re:This is the dumbest research I've seen this yea

[Anonymous Coward]

I like the way they compare making your own "buffer" in the least efficient way, then writing it to disk with the runtime's buffered I/O, vs just using the runtime's buffered I/O. So they didn't even test the disk's performance. With Python it could be a simple newbie mistake, but the Java code has explicitly added buffering.

This article's either an outright lie, or a result of gross incompetence. Probably both.

Selected the wrong datatype = poor programmer

[CraigCruden]

So they basically selected a bad datatype and wrote a very inefficient program to handle manipulation of data and they use that as the basis to say that memory was the issue. The issue was programming without thought to what the computer was actually doing. Is this what these two Universities are teaching their students? Were they being purposely bad programmers to prove a point?

God help the world if these people ever have to program efficiently....

How the mighty have fallen

[ChaoticCoyote]

Slashdot has fallen far in credibility if it promotes sloppy research like the referenced article.

Re:How the mighty have fallen

[Anonymous Coward]

Indeed.

*Adds slashdot to blacklist on all routers throughout the company and my home*

Re:How the mighty have fallen

[hcs_$reboot]

Promotion for discussion, a flamebait article that brought ~500 posts AON. Not bad.

Re:How the mighty have fallen

[houghi]

And the 4 minute rule doesn't help to have a discussion either. That is why you see in the history 1000+ message discussion where we now get hardly to 500 on very hot toppics.

Basically it means we are here just to click on the ads and shut up for the rest.

This is research??

[Anonymous Coward]

University of Calgary and the University of British Columbia must not be very good Computer Science schools.

Re:This is the dumbest research I've seen this yea

[falzer]

>According TFA, they actually do an explicit sync to disk at the end of the writes. So it's not purely writing into cache.

The code in the paper says they flush before closing the file. This is not the same as a sync. They don't even flush (or sync) after each write.

Why does the JIT compiler not optimize this ?

[Anonymous Coward]

doesn't the compiler see that the old string memory location is no longer being used and can thus be reused for the next string ? The last decade it seems to me that compilers have gotten worse and worse. worst was android studio that takes minutes to build a simple project and it doesn't even need to do any compiling.

Perhaps they had crappy chips?

[Anonymous Coward]

There are huge differences in memory chips. Some brands have enormous error rates, which considerably slow down the system they are installed in. I don't see any reference to what kind of memory they used. I do notice that the words ECC and Registered do not appear anywhere in the reports. Anyone doing serious computing should invest in Registered ECC Memory and a motherboard that properly supports it. The time you save may be your own. Didn't Einstein prove that Money (M) equals Time (T) plus Effort (E) squared? m=te Or was is Pythagoras?

Re:Perhaps they had crappy chips?

[Anonymous Coward]

My squared symbol did not show up in my post. Used the Alt 253 code to make squared symbol in my m=te equation. Anyone know a better way to make a superscript 2?

Reading helps

[Kleanthes]

While it is nice to point out that the code sucks, they do already know that. They mention StringBuilder on page 6, for example. No problem there. But of course, in the end, the paper has nothing to do with disk vs. memory. It's about comparing one O(n^2) algorithm to an O(n) algorithm and determine that one of them is quicker. The problem is, that it has nothing to do with where you save your data. The basic point, that bad code makes stuff slow is true, but, if you ask me, told quite confusingly.

Epic Troll

[Anonymous Coward]

Jesus H. CHrist, this is a blatantly sexist and epic troll.

But I can't disagree with the argument. 100% correct on all points.

Perhaps you should read their conclusions.

[Anonymous Coward]

Go back and read their conclusions and then think about how much of you flaming is actually the point they are making.
I've never bothered posting here before, but this is pathetic.
You're all so busy trying to look smart (about something blatantly obvious) that you clearly haven't taken the time to even read the conclusions.
Make's you look pretty silly to me!

That is the biggest pile of shit

[Anonymous Coward]

It does NOT do heavy disk access; both version buffer in RAM before writing to disk a single time.

It just shows that the OS buffering is more efficient, for that use case, than the language string manipulation.

some kind of Special Canadian Memory

[user.aaaaa]

yea

After doing large matrix transforms

[Anonymous Coward]

on multiple 1000x1000 COMPLEX*16 arrays, and watching the machine page-fault itself nearly into oblivion, I call bollocks.

April 1st is a bit early this year!

[SLOGEN]

Wow, April 1st came early this year,... although I can't spot any obvious prank names....

I sincerely hope this is a prank, even if it's apparently from a biology department.

Re:April 1st is a bit early this year!

[hcs_$reboot]

Unfortunately that's serious "research". An article made from people who learned how a computer works through java and python. This is what you can expect.

FML

[krkhan]

I opened the link and found that I share my first name with the first author. How am I supposed to live with this now?

Re:This is the dumbest research I've seen this yea

[brausch]

Even worse, they were not just concatenating the strings in memory. They were making a new string each time and copying the old one first, then concatenating. Their choices of computer languages and their lack of understanding of those choices makes this a problem.

Junk science

[compudj]

Wow. Has anyone heard about buffered writes ? And does kernel-level page cache ring a bell ? No fsync was ever used in the benchmarks, therefore, it is never actually hitting the disk. The only good thing about this paper is that the Java and Python listings are available at the end, for everyone to identify the basic flaws in this research.

So yeah, it's faster to write directly to MEMORY than to do a copy before writing to MEMORY.

Re:This is the dumbest research I've seen this yea

[c]

Well, that's pretty lame then. They did say "sync" in the paper, but I didn't get to the actual code since, quite frankly, I was being blinded by the daylight already coming through the holes in the rest of the paper.

The world is at the verge of destruction

[Anonymous Coward]

Please, please, for the love of $DEITY, nobody tell them about mmap'ing a file! That will make their brains go supernova!

Java 101

[Anonymous Coward]

Use a StringBuilder. Go back to school newbs.

Quite Possibly The Worst Paper I've Ever Read

[Anonymous Coward]

Really? They published this with their names on it?
The only thing they've proven is that a bad algorithm can be slow.
We've known that for quite a while now.

You are incorrect

[Anonymous Coward]

No, java uses StringBuilder in java 1.7 & 1.8
class a {
        public static void main(String [] args)
        {final String b=args[0],c=args[1];final String a=b+c;}
}
then compile and disassemble bytecode

javac a.java
javap -c -private a
slashdot prevents printing the {} characters
as you see from the bytecode
it it basically
a=new StringBuilder().append(b).append(c).toString()
  java -version
java version "1.7.0_75"
OpenJDK Runtime Environment (fedora-2.5.4.2.fc17-x86_64 u75-b13)
OpenJDK 64-Bit Server VM (build 24.75-b04, mixed mode)

Re:You are incorrect

[Anonymous Coward]

relevant bytecode
    8: new #2 // class java/lang/StringBuilder
            11: dup
            12: invokespecial #3 // Method java/lang/StringBuilder."":()V
            15: aload_1
            16: invokevirtual #4 // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
            19: aload_2
            20: invokevirtual #4 // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
            23: invokevirtual #5 // Method java/lang/StringBuilder.toString:()Ljava/lang/String;

arXiv is NOT peer reviewed...

[Anonymous Coward]

Anyone can upload an article to arXiv.
In the case of this particular piece of "work," it is obvious that no revision took place.
This can be hardly considered research and it should not appear in slashdot or in any other media... unless for entertainment reasons.

Why use a language with garbage collection

[Anonymous Coward]

Why would you run this test in Java and Python? I love python, but I wouldn't use it for a memory performance test. I would use a language where I know, and control, what is happening with memory management. IMHO, that makes the entire experiment suspect and, most likely, useless.

I only skimmed through it, but I did see things like :
string = string + "1"

The performance of that depends entirely on how the python interpreter is implementing this operation. It could be doing something sub optimal... you don't know. Figuring out what is happening is a research project in and of itself. If the experiment were performed in C, we'd have real data.

As a side note, the article did say something about memory being faster, which it is, but the overall time was slower, from start to finish. I do wonder how the JIT compiler in Java and the python interpreter are effecting this. That issue is not limited to parsing either. Again, another reason this should have not been done in those languages.

As someone who has written code to do performance testing on both RAM and FLASH before, this article flawed. They might have some point. But. the article doesn't make it.

Fixed

[Hardhead_7]

http://pastebin.com/wJuWeAiN

In-Memory takes .1 seconds.
Writing to Disk takes .4 seconds.

No programming knowledge required to debunk this

[wendyo]

Just look at their chart, they are comparing apples to oranges. Their "memory test" is shown as string concactination time plus write to disk time [they break it into two columns]. Disk test is write to disk time.

This is like saying it takes longer to walk to the store if you make a pair of shoes first than if you just walk to the store.

RTFM

[Anonymous Coward]

From the python wiki - https://wiki.python.org/moin/PythonSpeed/PerformanceTips:

Avoid this:

s = ""
for substring in list:
        s += substring

Use

s = "".join(list)

instead. The former is a very common and catastrophic mistake when building large strings. Similarly, if you are generating bits of a string sequentially instead of:

s = ""
for x in list:
        s += some_function(x)

use

slist = [some_function(elt) for elt in somelist]
s = "".join(slist)

java string concatenation is O(N)

[bingoUV]

This "researcher" is an idiot. The java code given at the bottom of the "research paper" uses + operator to concatenate strings. This is O(N) in Oracle java. Total algorithm becomes O(N*N) in memory, and O(N) on disk.

Obviously N*N takes longer than N after a certain N even when N*N is running on faster memory.

BufferedWriter in java

[Anonymous Coward]

They published the code Java code was using a bufferedwriter - which will reduce the amount of disk IO so effectively they are testing it in memory - then testing it in memory?

More mod commentary required?

[uarch]

I'm wondering if we need to find a means of enforcing at least some level of fact checking and commentary from the mods.
Simply re-posting this submission as is has turned into a giant flame fest because the research was crap. (As is a frighteningly large proportion of comp-sci & comp-eng research these days).

If the mods are decent then they should be able to take a moment to look through this, understand how much of a train-wreck it is and provide a bit of commentary to prevent the flame-fest or outright reject it. (I'm already on the site so a crap article isn't going to bring any additional add revenue. It will simply drive traffic elsewhere after the first few people identify it as crap.)

Yes, yes. I know. That isn't what our mods do...

Maybe it's time they started...

No StringBuilder used

[Anonymous Coward]

for (int i = 0; i numAdd; i++) {
  addString += "1";
}

for (int i=0; i numIter; i++) {
  concatString += addString;
}

Seriously ?

It should use a StringBuilder buffer, this is highly inefficient in Java.

Doesn't happen afaik in Delphi though

[Anonymous Coward]

Year ago in a some of Delphi Object Pascal projects (both personal & professional ones) I changed classic oldschool Turbo Pascal File I/O methods like:

AssignFile
Reset
Append
Rewrite
ReadLn
WriteLn
Flush
CloseFile

For File I/O to their "fully qualified" System Unit API based analogs of:

System.AssignFile
System.Reset
System.Append
System.Rewrite
System.ReadLn
System.WriteLn
System.Flush
System.Close

They're "straight-to-API" abstracted/based methods (vs. std. 'oldschool/classic' Turbo Pascal methods).

I did so, & on the very note you mention (looking for speed & efficiency gains in file routines)!

I didn't see a change in .exe size OR execution speeds (I profile using oldschool methods of registering a hi-res multimedia timer with the OS to test these @ the START & END of each routine involved to test (yea, primitive but it works)).

That essentially told me that Borland/Embarcadero's compiler designers did the RIGHT THING for their compiler/linker really - not doing extra work for no good reason + using the MOST EFFICIENT METHODS abstracting even the oldschool syntax to the most efficient API based types.

* However, I did see a BIT quicker compilation time (fully qualified naming probably helped there), & I ended up sticking by the API based ones from the System Unit since then actually (just to be 'safe') & use the API itself (most of its built-in to Delphi as it is in C++ dialects usually, unlike languages like VB was where you had to use "declare" to use the API).

APK

P.S.=> I didn't like reading here & hearing other languages do NOT abstract out to the API methods (which is all they're going to do from the language methods anyhow in the end really - iirc, folks here "zeroed-in" largely on Python, Java maybe some others mentioned by others here - since I've used them over time academically or professionally myself in development projects on contract I was semi-concerned even though they worked & it was LONG ago) - Again - That's taking extra steps passing to the OS that way afaik & inefficient... apk

Delphi's not like that though... apk

[Anonymous Coward]

Year ago in a some of Delphi Object Pascal projects (both personal & professional ones) I changed classic oldschool Turbo Pascal File I/O methods like:

AssignFile
Reset
Append
Rewrite
ReadLn
WriteLn
Flush
CloseFile

For File I/O to their "fully qualified" System Unit API based analogs of:

System.AssignFile
System.Reset
System.Append
System.Rewrite
System.ReadLn
System.WriteLn
System.Flush
System.Close

They're "straight-to-API" abstracted/based methods (vs. std. 'oldschool/classic' Turbo Pascal methods).

I did so, & on the very note you mention (looking for speed & efficiency gains in file routines)!

I didn't see a change in .exe size OR execution speeds (I profile using oldschool methods of registering a hi-res multimedia timer with the OS to test these @ the START & END of each routine involved to test (yea, primitive but it works)).

That essentially told me that Borland/Embarcadero's compiler designers did the RIGHT THING for their compiler/linker really - not doing extra work for no good reason + using the MOST EFFICIENT METHODS abstracting even the oldschool syntax to the most efficient API based types.

* However, I did see a BIT quicker compilation time (fully qualified naming probably helped there), & I ended up sticking by the API based ones from the System Unit since then actually (just to be 'safe') & use the API itself (most of its built-in to Delphi as it is in C++ dialects usually, unlike languages like VB was where you had to use "declare" to use the API).

APK

P.S.=> I didn't like reading here & hearing other languages do NOT abstract out to the API methods (which is all they're going to do from the language methods anyhow in the end really - iirc, folks here "zeroed-in" largely on Python, Java maybe some others mentioned by others here - since I've used them over time academically or professionally myself in development projects on contract I was semi-concerned even though they worked & it was LONG ago) - Again: That's taking extra steps passing to the OS that way afaik & inefficient... apk

Didn't see that with Delphi here... apk

[Anonymous Coward]

Year ago in a some of Delphi Object Pascal projects (both personal & professional ones) I changed classic oldschool Turbo Pascal File I/O methods like:

AssignFile
Reset
Append
Rewrite
ReadLn
WriteLn
Flush
CloseFile

For File I/O to their "fully qualified" System Unit API based analogs of:

System.AssignFile
System.Reset
System.Append
System.Rewrite
System.ReadLn
System.WriteLn
System.Flush
System.Close

They're "straight-to-API" abstracted/based methods (vs. std. 'oldschool/classic' Turbo Pascal methods).

I did so, & on the very note you mention (looking for speed & efficiency gains in file routines)!

I didn't see a change in .exe size OR execution speeds (I profile using oldschool methods of registering a hi-res multimedia timer with the OS to test these @ the START & END of each routine involved to test (yea, primitive but it works)).

That essentially told me that Borland/Embarcadero's compiler designers did the RIGHT THING for their compiler/linker really - not doing extra work for no good reason + using the MOST EFFICIENT METHODS abstracting even the oldschool syntax to the most efficient API based types.

* However, I did see a BIT quicker compilation time (fully qualified naming probably helped there), & I ended up sticking by the API based ones from the System Unit since then actually (just to be 'safe') & use the API itself (most of its built-in to Delphi as it is in C++ dialects usually, unlike languages like VB was where you had to use "declare" to use the API).

APK

P.S.=> I didn't like reading here & hearing other languages do NOT abstract out to the API methods (which is all they're going to do from the language methods anyhow in the end really - iirc, folks here "zeroed-in" largely on Python, Java maybe some others mentioned by others here - since I've used them over time academically or professionally myself in development projects on contract I was semi-concerned even though they worked & it was LONG ago) - Again - That's taking extra steps (From "form" or classic methods then to API & OS) passing to the OS that way afaik & inefficient... apk

Delphi Object Pascal Flush vs. System.Flush IO

[Anonymous Coward]

Delphi's Object Pascal's not like that @ least. I found out Years ago in a some of Delphi Object Pascal projects (both personal & professional ones) I changed classic oldschool Turbo Pascal File I/O methods like:

AssignFile
Reset
Append
Rewrite
ReadLn
WriteLn
Flush
CloseFile

For File I/O to their "fully qualified" System Unit API based analogs of:

System.AssignFile
System.Reset
System.Append
System.Rewrite
System.ReadLn
System.WriteLn
System.Flush
System.Close

They're "straight-to-API" abstracted/based methods (vs. std. 'oldschool/classic' Turbo Pascal methods).

I did so, & on the very note you mention (looking for speed & efficiency gains in file routines)!

I didn't see a change in .exe size OR execution speeds (I profile using oldschool methods of registering a hi-res multimedia timer with the OS to test these @ the START & END of each routine involved to test (yea, primitive but it works)).

That essentially told me that Borland/Embarcadero's compiler designers did the RIGHT THING for their compiler/linker really - not doing extra work for no good reason + using the MOST EFFICIENT METHODS abstracting even the oldschool syntax to the most efficient API based types.

* However, I did see a BIT quicker compilation time (fully qualified naming probably helped there), & I ended up sticking by the API based ones from the System Unit since then actually (just to be 'safe') & use the API itself (most of its built-in to Delphi as it is in C++ dialects usually, unlike languages like VB was where you had to use "declare" to use the API).

APK

P.S.=> I didn't like reading here & hearing other languages do NOT abstract out to the API methods (which is all they're going to do from the language methods anyhow in the end really - iirc, folks here "zeroed-in" largely on Python, Java maybe some others mentioned by others here - since I've used them over time academically or professionally myself in development projects on contract I was semi-concerned even though they worked & it was LONG ago) - Again - That's taking extra steps (From "form" or classic methods then to API & OS) passing to the OS that way afaik & inefficient... apk

Not completely useless...

[Lodragandraoidh]

They should have viewed this presentation about increasing a python data crunching application 114,000 times faster before they set off on their research project.

To summarize - there are a multitude of ways to optimize your application including using the chip's onboard cache to avoid the overhead/delay of accessing memory on the motherboard across the bus

Yes - as we try to eek out more performance from our applications - we'll need to consider the relationship between our applications and the underlying implementation and capabilities of the hardware it lives on. Further - I would say we also should be considering how to make our tools do this sort of thing for us. Given the complexities we are seeing in the development arena today, including virtualization, the need to do more with less both on the back end, as well as on small hand held devices, and the need to build more faster while increasing security of what we build, I consider it imperative.

Has anybody here actually read the paper?

[Anonymous Coward]

Based on the comments here, I doubt if many people actually read the paper with any amount of attention before joining the mob with pitchforks.

The authors clearly know Java Strings are not the best thing for concatenation. They even mention StringBuilder as a way to fix the performance problem. This is an example of how things can go wrong if not careful. It is great that so many slashdotters already know their Java Strings so well, but does everybody know their Python, Haskell, etc. too.? The paper is making a general point using a specific example.

  A lot of posters mention the problem being comparing an O(N^2) algorithm with an O(N) algorithm. If you read the paper you'll notice that the string concatenation loop they use looks like this:
for (int i=0; i numIter; i++) {
                concatString += addString;
}
    The running times don't change in a quadratic way, because in their code numIter * length(addString) is always 1,000,000. As the outer loop gets bigger, the concatenated string gets smaller.

The difference in running times comes from the number of string concatenations (the outer loop), and it is clear that as the number of concatenations drops, performance gets better. This indicates that the problem is caused by the immutable String objects, which need to be reallocated and re-initialized. The more this needs to be done, the poorer the performance, as pointed out in the paper.

  Speaking of complexity, does anyone know what is the complexity of their disk-only code below?
for (int i=0; i numIter; i++) {
                        writer.write(addString);
}
  The for loop goes over N items, while write() must loop over the length of addString == O(N^2)? In any case, here again numIter * length(addString) is always 1,000,000.

I believe the paper is simulating creating a file in memory and then writing it to disk as opposed to writing the strings to disk as soon an the strings are generated. The alternative/clever ways of generating a string of 1,000,000 "1"s like concatString = addString * numIter are useless in this case, because in reality addString may contain unique data bits and pieces.

There are some unexpected results with the paper's Python tests. The considerable performance differences under Windows and Linux with the same code, or when rearranging a concatenation order are interesting. This paper is actually worth a careful read, even if most of us would never write code that heavily uses Java Strings concatenation!

Re:Has anybody here actually read the paper?

[Anonymous Coward]

I agree. People are jumping to conclusions about this paper without having read it carefully. How many people have mentioned using StringBuilder when the paper itself mentions that? The answer: too many. I am now tempted to write a paper on herd mentality among some people and put it on arxiv to see what happens on Slashdot :-)

  Seriously though, it is interesting that the paper actually says "A developer familiar with the language and system internals readily notices the causes of this observed behaviour". It seems most of the posts here confirm what the paper is saying!! The rest, people who are not familiar with language and system internals, are not posting so they are not represented, but I am sure there are developers out there who are minimizing disk IO in the hopes of better performance. We can call them any names we want if it helps our egos, but the paper is by academic people who are probably involved in training developers. It is good to see they pay attention to such stuff and make sure all developers, not just us super clever and super knowledgeable Java GODs, are aware of these performance issues.

I actually want to see the paper published because it seems to be right in nearly everything it says, even if some of it is obvious to "A developer familiar with the language and system internals". The one problem with the paper is using buffered writers, because it make the disk time measurements unfair. If they don't use buffers in the disk code, then the paper is much improved.

Re:Has anybody here actually read the paper?

[lu-darp]

Let the pitchforks fly!! A paper has to present something non-obvious and of value, this fails on both counts.

I'm just waiting for the next article "Newsflash: solving a sudouk puzzle by hand is faster than software - under certain conditions"

Buffer overflow.

[Anonymous Coward]

Nice buffer overflow bug you've got there.

Java strings overweight? Citation?

[kervin]

People just say things on here and it's taken as fact. How is Java's String implementation overweight?

Java, like C# does use 16 bit char widths, but that actually makes it faster than variable width characters. That's why these languages do so.

So what about Java strings are 'overweight'?

Re:Java strings overweight? Citation?

[Spazmania]

Compared to how the C-based kernel handles its byte buffers after you've written to the file handle? You really need help understanding how java strings are overweight _by comparison_?

'Idiot coders produce slow code'

[Anonymous Coward]

FFS. I knew the researchers coding fuckup before I even read the code

BWAHHHHHHHHH

If you do it wrong in memory

[fluffynuts]

Expect the disk to be faster. For the privileged few who bothered to RTFA, you'll understand. The high-level languages used tend to degrade on the specific instructions (string concat) as the number of ops increases; I also wager that this problem is more prevalent on Windows where the memory manager is about as good useful as a clown who thinks he has an eye for fashion. So, distilled, this article should read:

"Researchers find an obtuse way to defy a well-established rule-of-thumb".

Bravo. Or not.

this is NOT news

[rewindustry]

the tests they show only serve to demonstrate how slow python string concatenation is.
they then go on to say that disk writes are bufferered more sensibly, and this is why they are faster.
the key thing to notice is that disk buffering happens in **memory**.

memory is still, and will remain, much faster.

you just have to use it properly.

hd cache

[Anonymous Coward]

Don't hard drives have more than 1 Mb of DIMM cache? Or has the onboard RAM disabled for the test?

I'll say it - Junk science!

[ebvwfbw]

Put this paper in the dictionary under junk science. This is stupid.

Send them to Mars;

[NewYork]

Send these researchers to Mars; They're very much needed there;

ArrayList and StringBuilder use this

[tepples]

I would realloc the buffer doubling the size each time it overflowed. This allocation strategy is simple, is bounded to 50% worst case overhead, and requires only log N reallocations for a maximum buffer size of N.

It also happens to be the policy used by Java's ArrayList and presumably by its StringBuilder.

Reminds me of calculating factorial with .bat file

[renergy]

Reminds me of one really strange course on college. The lecturer calculated factorial, up to ten - using DOS 6.22 .bat file. Actually, he provided three "solutions".
One solution was to write ten "if" cases, and just echo the corresponding number, hardcoded.
I can't remember the second solution.
The third was the real "beast". It was based on recursion. "factor.bat" called itself. The batch created one byte file in the beginning. And this file was joined n-times within each iteration. All this to facilitate multiplication, which was not directly achievable in a batch file. In the end, there was "dir /b fact.txt" and probably an echo with "look at the size, this is the result".
I kid you not. It was something like: for $1==1, fact.bat created a file "fact.txt", with one byte (using echo x > fact.txt) then the file was joined n-times - with type fact.txt >> xfact.txt after fact.txt was added n times to xfact, xfact would be renamed to fact.txt
Of course, in this case, disk access was really slower than pascal version, that run in memory... :)