String Operator Effeciency

Page: 1 2
ID:105170
 
Nov 30 2010, 9:37 am (Edited on Nov 30 2010, 1:15 pm)
Applies to:Dream Seeker
Status: Open
Issue hasn't been assigned a status value.
Would it be possible to improve the efficiency of adding to long strings? Trying to do this now causes a ridiculous amount of server sided lag - freezing the entire game. It can be reduced somewhat by portioning the text, or by splitting the end result into pages if possible. I'm not really sure why this is a problem in the first place. Shouldn't adding "a" to "a" take about the same power as adding "a" to "abc..."? You're simply pasting it at the end.
Dec 1 2010, 7:09 am
No. "abc..." takes six times the memory of "a" -- with longer strings,this takes that much longer.
Dec 1 2010, 8:33 am
It actually seems pretty functional if you just add long strings together. Its more a problem when you loop through long lists of things in an effort to compile a readable text format from them.
Dec 1 2010, 11:11 am
It's the number of concatenations that causes the problem not the size of the strings you're concatenating.

I often use concatenation a lot when generating HTML output. If it were to become an issue I could encode the data in JavaScript and have JavaScript perform the string concatenations needed to generate the formatted page. This offloads the work to the client (some of it at least, you still need to generate the JS code) but doesn't help if you're dealing with text output in output controls, alert messages, or stat panels.
Dec 3 2010, 5:12 am
Concatenating strings requires the following process:

1) Memory must be allocated for the result string.
2) The two strings are copied to memory.
3) The result is added to the string table.
4) The old strings, if no longer used, may be removed from the string table.

Basically you're doing a lot of allocation and deallocation, which is causing the slowdown. It's not trivial to optimize. BYOND does have internal classes it can use for concatenating strings in a faster way when it doesn't have to go through soft code, but I can't think of a way to optimize the soft code at all.

What might be optimizable is the way BYOND searches for new string IDs to use, which I could also say of objs, mobs, datums, etc.
Dec 27 2010, 5:13 pm
Why not, instead of trying to optimize the existing string implementation, take notes from the System.Text.StringBuilder class in .NET, which is a specialized class for building (e.g. through repeated concactenation) strings, IIRC.
Dec 29 2010, 6:29 am
We already have a specialized class for building strings. It may or may not be possible to improve on its efficiency, but the real issue here is not the builder but the way the strings have to be calculated and stored when doing a concatenation operation from soft code.

Where Falacy ran into problems was when trying to add strings repeatedly in a loop. In a language like C++ you can have a string builder open and only "close" the string when you know you're done; in fact we do that in a lot of places in BYOND's code. But because there's really no way to do that same thing in DM, the string has to be "closed" during each loop iteration.

This is potentially solvable but it could potentially introduce more inefficiency than it aims to prevent. The idea would be that we could create a special type for an open string being built, where using the += operator would just do the concatenation within the builder. Then any assignment of that var could convert it automatically to a closed string. That last part though is the real killer; it adds more logic to what's basically the simplest and also most common operation of all.
Dec 29 2010, 6:41 am
I'm not sure how efficiently lists are handled, but have you considered a built-in list to string proc? You append strings to the list (which shouldn't need to make copies of anything) then call the proc once to generate the complete result string. It's not as elegant as being able to use [] and have the concatenation handled nicely behind the scenes, but for the reasons you mentioned that might not be possible.
Jan 14 2011, 12:16 pm
Well this would be nice if it handled it in some way but may be un-realistic in certain circumstances for it to work in this way & even may cause issues, maybe you could tell strings when to be "Opened" & "Closed" yourself, if the developer isn't willing to put forth a little more effort to do it, do they really need the added efficiency?
Jan 14 2011, 5:19 pm
How long are the strings in this scenario? I'm testing a DLL that seems to exhibit better performance than DM, but the DLL interface BYOND has seems to be a bit finicky as well. =|
Jan 15 2011, 4:20 am
As an idea (which may be too tricky to execute) would be some semantic analysis on the compiler's part on strings. Assuming (big assumption if I understand the situation with the DM compiler) an AST, you can inspect looping sub-trees for string manipulation, and identify where strings are concatenated, and whether they at some point in the loop are read, then transform into an internal datum that handles this better accordingly.

However you've got a weakly typed language, so I'm guessing that kind of type info isn't available until you actually hit execution.
Jan 17 2011, 5:59 am
Yeah, I think this is pretty much impossible to do.
Jan 17 2011, 12:03 pm
Not to worry though, hopefully I can cover this fairly niche performance scenario in my String Utilities library in the future.
Feb 6 2011, 5:36 am
I'm not sure how your string utilities library works, but here's a fast DM implementation I came up with: http://www.byond.com/members/Forumaccount/forum?id=180

The proc takes a list of strings (ex: list("a", "b", "c")) and converts it to a single string (ex: "abc").
Feb 6 2011, 6:59 am (Edited on Feb 6 2011, 7:18 am)
(edit)
FYI: error handling was omited for readability, and I did not do any optimizations (not including the fact that the algorithm itself is for an optimization).

And after you get done with a bunch of concats, this is guaranteed to leave you with an amount of extra memory hanging around that is less than the length of the string itself. That is, the total memory consumed by the string after concats will always be less than twice the length of the resultant string that was generated.
(/edit)

Here, try a modification of this style in the Byond code. I just whipped that up in about 15 minutes at the most, but I know that it would take longer to actually update Byond in such a way.

This just always keeps extra space available so you don't have to allocate more every single time. This is one of the basic techniques that all modern speed optimizers do for situations like this.

This would allow Forum_account's example with 5000 strings being concatenated to only require about a dozen string allocations/deallocations, so it should handle that situation even faster than Forum_account's Byond softcode improvement.

#include <string.h>

/* base string type for this example */
struct quicklyExtendableString
{
    char *string;
    int arrayLength;
};

/* just a constructor to make a new one, and you tell it a size estimate of how long you think the initial string will be */
struct quicklyExtendableString *newQuicklyExtendableString(int size)
{
    struct quicklyExtendableString *newString = 0;
    char *arrChar = 0;
    /* let's start off on the right foot for efficiency from the beginning */
    size *= 2;

    /* short and straightforward, just allocate for the struct and the char array then set size */
    newString = (struct quicklyExtendableString*)malloc(sizeof(quicklyExtendableString));
    newString->string = (char*)malloc(sizeof(char)*size);
    newString->arrayLength = size;
    newString->string[0] = 0;

    return newString;
}

/* this does the concatenation */
void quickConcat(struct quicklyExtendableString *string, char *extra)
{
    char *oldString;
    int totalLength = strlen(string->string)+strlen(extra)+1;

    /* if the buffer would overflow, extend it, this is where I do the alloc/move/dealloc */
    if(totalLength > string->arrayLength)
    {
        /* keep track of the old one */
        oldString = string->string;
        /* get a bigger buffer and make it the new one */
        string->string = (char*)malloc(sizeof(char)*totalLength*2);
        string->arrayLength = totalLength*2;
        /* move the old one over */
        strcpy(string->string, oldString);
        /* dealloc the one we don't need anymore */
        free(oldString);
    }

    /* whether we increased or not before this, just concat the new stuff */
    strcpy(string->string+strlen(string->string), extra);
}
Feb 6 2011, 6:17 pm
Allocating extra space with each string is doable, although it's wasteful in most cases. The bigger issue though is that without specifically applying only to the += operator, and only acting on strings that have exactly one reference, this method just can't work. The amount of extra space would also need to be guessed in advanced, and a wrong guess would mean wasting a lot of memory and/or compacting later. As a general rule allocating extra space for strings would simply be a big waste of memory, and the one scenario where having the extra space would be helpful would be uncommon enough as to make the tradeoff for speed too costly.

Really the only way to do this right would be to use a built-in string concatenation class for temporary strings, that could be converted to strings on a moment's notice. BYOND's built-in string builder actually does do the extra space allocation you describe, but the problem as I already described is that without having a special internal type like this, DM has no idea when to "close" the string. Even with a type like this it'd be fairly important to only keep a string builder open as long as was necessary, and close it at the first opportunity. Assigning a concatenation to a new var for instance should close the string, but checking for that at assignment time is really not ideal.
Feb 7 2011, 3:16 am
My concat proc is sufficient for the cases where you are repeatedly adding strings onto the end of another. For the cases where you aren't simply adding onto the end of one string you're correct that all optimization would have consequences for their wrong assumptions. If there was no consequence all strings would behave this way and there'd be no need for string buffer objects.

For a nicer syntax and the built-in documentation, it would be nice to have it called list.Join and take an argument that is a delimiter placed between each pair of strings in the list. A built-in implementation could also make slightly better use of your internal string buffers.
Feb 7 2011, 3:47 am
Lummox JR wrote:
Allocating extra space with each string is doable, although it's wasteful in most cases.

No, it's not.

The amount of extra space would also need to be guessed in advanced, and a wrong guess would mean wasting a lot of memory and/or compacting later. As a general rule allocating extra space for strings would simply be a big waste of memory,

Your guess should always be the currently required length times 2. There is not a lot of wasted memory; as I said, the unused memory will always be less than or equal to twice the actual length of the current string. That is not a big waste at all. Your memory usage is, on average, 150% what it would otherwise normally be, and you get insane speed boosts on average. There is almost never a speed decrease with this method, and even when there is, it is almost imperceptible.

Insignificant performance loss, even in the worst case scenarios, insane performance boosts in the best case (log(n) compared to n), and no perceptible change in the average case. Pros up the wazoo, and the only con is that you use up 50% more memory on strings, twice as much worst case.

and the one scenario where having the extra space would be helpful would be uncommon enough as to make the tradeoff for speed too costly.

The tradeoff is not costly at all. Changing the worst case efficiencty of one thing from n to 2n to be able to change the worst case for something else from n to log(n) is not costly at all.

Even if you apply this and the reverse of this for shortening strings, then when strings get smaller you can check to see if the actual string's size is less than the array length /2, then allocate a shorter string.

There are obscenely great benefits to be had from this, and the cons are small enough to sneeze at even in the worst case scenario. This is not a free lunch, but it's very, very close; it's like a 10-cent lunch.

Even if you do this and nothing else for your string manipulations, the resulting system, though not fully optimized, would still be better than what you have currently.
Feb 7 2011, 4:12 am (Edited on Feb 7 2011, 5:01 am)
Asymptotic bounds are theoretical, the amount of RAM I have is not. While it's nice to ignore coefficients and say "c'mon, log n is better than n and the memory usage is still O(n)" the truth is that when you're dealing with actual programs running on actual hardware, those details matter.

I would expect that most concatenation is done using square braces to embed expressions and the result is not cumulative (you're not building a large string piece by piece). Most of the time you're just writing things like "hi [mob.name], how are you?" Your change would offer no improvement for these cases (because this is handled efficiently already) but would double the amount of memory used to store every objects icon state (because you never know when it might be appended to).

Edit: The concatenations that are not handled efficiently can be handled just fine by my concat proc. Why have BYOND make costly assumptions about what might happen to a string? Just give the developer control.
Feb 7 2011, 5:10 am
Forum_account wrote:
Asymptotic bounds are theoretical, the amount of RAM I have is not. While it's nice to ignore coefficients and say "c'mon, log n is better than n and the memory usage is still O(n)" the truth is that when you're dealing with actual programs running on actual hardware, those details matter.

You misunderstand me if you think that is all my argument entails. I am specifically stating the details, I am not overlooking them.

The amount of RAM you have is indeed not theoretical, and you have to be careful about how much you use. But the amount of processing power you have is even more limited. In modern computers, we can afford to waste a little memory, but we can not afford as much to waste a little speed. Users do not notice that you are using up another couple megabytes of their memory, but they do notice when you are taking 4-8 seconds to process something instead of 0.04-0.08 seconds, which is the situation that caused you to make your initial posts in the first place, Forum_account.

The very worst case scenario for your memory is that your game's memory requires almost exclusively text strings and has a ton of them. This is a ridiculous worst-case scenario, but it is the worst case nonetheless, and in this case, let's assume your game takes up a whopping 1GB of memory (unheard of for the vast majority of Byond games) and you have actually hit the worst case for every single individual string you have, so it takes 2GB instead. As long as your server has more than 2GB of memory, you don't notice a thing. That's worst case.

Worst case for the existing system is that the processing time can grow without bound and your game can become unplayable unless you take it upon yourself to deal with it on our side.

Byond's entire premise is that it is supposed to make game development much easier, so it fits with the master plan to handle this internally to Byond instead of externally. If you're going to use Byond, you should not have to worry about things like this. If you have to keep finding crafty ways to just make your game work in the first place, you might as well not use Byond for that specific game.

I would expect that most concatenation is done using...

Based on the discussions that have taken place here, my understanding is that, internally, every time Byond sees a text string manipulation, it handles the entire statement's worth of manipulations at once. That is, if you do "[a][b][c][d]" it is not going to have to reallocate a new text string 4 times, instead it will just build up 1 text string and is therefore more efficient.

If you do a+b+c+d, I think that it has been alluded to that it will also handle this properly since it is all in one statement. I'm not going to bother checking; which side of the fence this case falls on doesn't really change the argument any, but still, the point is that it handles some cases properly, as long as it is easy to tell ahead of time that there will be one resulting string with multiple manipulations.

But at the end of any given statement like that, it finalizes the string and leaves it with just enough memory allocated for the actual string, so if you ever want to add on to it again it has to realloc.

For my suggestion of just keeping extra space (always guaranteed to not be more than twice what is needed), it allows for growth room (or shrink room when going the other way and using the inverse of this) without having as many allocs. In this situation, it is literally log(n) vs n, no significant distinctions in constant. I cannot think of a situation where this would have any noticeably negative impact on speed. This does nothing but help speed, not hinder it.

The ONLY downside, which it isn't even much of one, is the slightly higher memory usage, and it's not even much more. We can afford to throw away a little bit of memory space, as that barely impacts the performance at all, but we cannot afford to throw away processing time.

I will break it down into extremely basic terms here, as there is not really any argument to be had against this:

The improvement basically has zero extra processing time even in its worst case scenarios vs the current methods best case scenarios.

The current method basically has infinite extra processing time for its worst case vs improvement's worst case.

The methods have the same processing time for average case.

The improvement uses twice the memory (only for strings) for its worst case scenario.

The improvement uses the same amount of memory for its best case scenario.

The improvement uses more than 1.5 times as much memory for its average case scenario.

This never hurts speed, it only helps speed. This has a slight, but completely acceptable, impact on memory.

The amount of users that are going to need that extra little bit of memory is going to be a group even smaller than the amount of users who need extra speed.

And if you fall into that little group where that extra bit of memory is required (you have 2GB worth of text strings and only 3GB of available RAM), it's a lot, lot easier and cheaper for you to add more memory than it is for someone else to speed up their computer.

AND on top of all that, there are other optimizations that you could apply to this as well so that many text strings use their best-case (array size is equal to the length of the text string) memory usage. It wouldn't take me long to optimize my example so that text strings which never get concatenated to always have arrays sized exactly for them. And with some effort, you could probably obtain a scenario where you have the speed benefits of my example while having an average case of memory usage close to the best case. I can think of several optimizations off the top of my head. This really is not that difficult.
Page: 1 2