News for hackers. Stuff that matters.
Re:Strings Are Evil by ocdtrekkie on Wednesday June 20, 2018 @12:28PM (#17356872)
I'm not in a scenario with any of my .NET code where this level of optimization is actually useful/valuable, but this was a pretty interesting read. It made me ponder a bit about how I handle strings in my code. I might try a couple of things for fun.
Re:Strings Are Evil by dahart on Wednesday June 20, 2018 @01:20PM (#17357402)
I'm currently in extreme optimization mode in C++, and even assembly & hardware some days. BUT -- the first rule of optimization is to only fix measurable, perceivable problems. This article was fun, but it didn't measure the right thing. The sum of all allocated memory is an almost useless metric, it doesn't reveal a problem to fix, and reducing it doesn't necessarily result in perceivable improvements.

I love Michael Abrash's introduction to the philosophy of optimization in the Black Book of Graphics:

"Before we can create high-performance code, we must understand what high performance is. The objective (not always attained) in creating high-performance software is to make the software able to carry out its appointed tasks so rapidly that it responds instantaneously, as far as the user is concerned. In other words, high-performance code should ideally run so fast that any further improvement in the code would be pointless.

Notice that the above definition most emphatically does not say anything about making the software as fast as possible. It also does not say anything about using assembly language, or an optimizing compiler, or, for that matter, a compiler at all. It also doesn’t say anything about how the code was designed and written. What it does say is that high-performance code shouldn’t get in the user’s way—and that’s all."

http://www.jagregory.com/abrash-black-book/#introduction

Re:Strings Are Evil by ocdtrekkie on Wednesday June 20, 2018 @02:00PM (#17357886)
It seemed to me the author had a clear problem and objective. That the import process has to take place outside of business hours because of it's memory usage. So wasn't reducing memory exactly the goal here? And doesn't reducing it then make it possible to do the import during business hours? (Which is arguably, far more instantaneous to users than "thanks, we'll process this tonight when we have memory available".)
Re:Strings Are Evil by dahart on Wednesday June 20, 2018 @02:10PM (#17358000)
Make sure to look over the table at the end. They saved 2 seconds of run time. They didn’t reduce much memory, they reduced heap allocations. It’s the same as allocating and then releasing a 1MB array 1000 times and then worrying that you’ve used a gigabyte, even though the most you ever had allocated was 1MB.
Re:Strings Are Evil by ocdtrekkie on Wednesday June 20, 2018 @02:19PM (#17358086)
I would argue reducing the time spent and memory used both by 25% is pretty significant, considering this is one of presumably a large number of jobs.

The comments on the article also state: "With regards to time taken and peak working set, that was not our main focus. Our main focus was to reduce the number of allocations and reduce the time spent in GC. Unfortunately this data import process is not a standalone one time application. It is a part of a much larger application which is core to our entire platform."

It's possible that this has no meaningful impact to their application, but it's far more likely that the blog author just hasn't provided you all of the information you need to understand why it's important. I feel reading charitably is the best case here.

Re:Strings Are Evil by dahart on Wednesday June 20, 2018 @03:27PM (#17358842)
25% is great! You're right, there might be more here, and it's always a good idea to be charitable in your reading, that's absolutely worth keeping in mind.

It's just that the headline sales pitch of the post is "from 7GB to 32KB". Unfortunately, that doesn't mean much and it's misleading. As is the title "Strings are evil". Those sentences combined with no obvious reason to ignore the primary optimization metrics and instead focus on something that doesn't affect either memory usage or run time very much, those things together make me feel like it's more likely the author either wanted a good blog post, or doesn't have a ton of experience with optimization. Those are both great, but that's no reason for me not to comment and try to add some clarity.

To me it seems a bit strange to say that time taken was not the main focus, and follow that with "reduce the time spent in GC." The singular primary reason to reduce allocations is to reduce run time of the program, there is no other reason here.

FWIW, it's highly likely that this program's run time could be further improved by more than 2x by allocating a single buffer the size of the file and doing a single fread() call, then processing the entire file in memory. That would increase the working set from 16MB to 300MB, or whatever the file size is, but would allow much faster processing than line buffered input.

Re:Strings Are Evil by megaman22 on Wednesday June 20, 2018 @12:37PM (#17356946)
It's sometimes amazing what low-hanging fruit can be kicking around that you didn't realize until you actually strap up a profiler to something.

The other day I was trying to figure out why one web request in an application was taking an absurd amount of time. I started looking at SQL queries and other external calls, only to realize that it turned out to be a logging statement that used a little innocent looking helper function to stringify a List<T>. Except it was using concatenation, with Aggregate e.g. Aggregate("", (a, b)=> a + b + ", ")... Replace that with a StringBuilder, and I went from seconds to milliseconds on that call. It's one of those things that you go "Eh, I'm just doing this on a few items, it'll be fine", and then month or years later, the wheels come off because something happens to try using it with tens of thousands of items.

Re:Strings Are Evil by chriswarbo on Wednesday June 20, 2018 @02:46PM (#17358414)
Concatenating strings like this is known as "Shlemiel the Painter's Algorithm", since each concatenation starts back at the beginning of the string.

From https://www.joelonsoftware.com/2001/12/11/back-to-basics

> Shlemiel gets a job as a street painter, painting the dotted lines down the middle of the road. On the first day he takes a can of paint out to the road and finishes 300 yards of the road. “That’s pretty good!” says his boss, “you’re a fast worker!” and pays him a kopeck.

> The next day Shlemiel only gets 150 yards done. “Well, that’s not nearly as good as yesterday, but you’re still a fast worker. 150 yards is respectable,” and pays him a kopeck.

> The next day Shlemiel paints 30 yards of the road. “Only 30!” shouts his boss. “That’s unacceptable! On the first day you did ten times that much work! What’s going on?”

> “I can’t help it,” says Shlemiel. “Every day I get farther and farther away from the paint can!”

The more general problem is being "accidentally quadratic", e.g. assuming that N concatenations will be O(N), but it's actually O(N^2) because each must traverse the intermediate string, and (assuming each input string has O(1) length) that intermediate string will have length O(N). There's a Tumblr blog at https://accidentallyquadratic.tumblr.com which collects examples of this, but I can't seem to get past Tumblr's GDPR landing page to see it.

Re:Strings Are Evil by usea on Wednesday June 20, 2018 @02:06PM (#17357951)
I've written that logging code, and over the years I've used both the StringBuilder and Aggregate styles. I've discovered that string.Join(", ", list) is a great fit for this, too. It's as quick as using StringBuilder, and also concise and composable (tastes may vary).