[510 pls]Optimize datum variable accessing

Page: 1 2 3 4
Feb 5 2016, 10:33 am
Yeah, I can understand that. In a game like yours it's hard to balance that kind of thing.
Feb 5 2016, 5:04 pm
Well probably the main problem of memory in ss13 is using regular variables to hold Boolean values or such
Feb 5 2016, 6:10 pm
Well probably the main problem of memory in ss13 is using regular variables to hold Boolean values or such

TBH, booleans aren't well optimized in many languages. One strategy for dealing with booleans is generally just avoiding them completely. Where you can get away with it, combine multiple related booleans into bitflags.

Another issue I have with booleans being used frequently is that I see them misapplied quite a lot. Like, this is something that I see pretty often:

mob
    var
        is_stunned = 0
        is_frozen = 0
        is_rooted = 0
        in_menu = 0
        is_paralyzed = 0
        is_dead = 0
    Move()
        if(is_stunned||is_frozen||is_rooted||in_menu||is_paralyzed||is_dead) return 0
        . = ..()
    proc
        stun(duration)
            is_stunned = 1
            sleep(duration)
            is_stunned = 0


One way of dealing with this is to make this all a single bitflag:

#define STATUS_STUNNED 1
#define STATUS_FROZEN 2
#define STATUS_ROOTED 4
#define STATUS_MENU 8
#define STATUS_PARALYZED 16
#define STATUS_DEAD 32
mob
    var
        status = 0
    Move()
        if(status) return 0
        . = ..()
    proc
        stun(duration)
            status |= STATUS_STUNNED
            sleep(duration)
            status &= ~STATUS_STUNNED


Though, to be honest, IMO an even better solution is simply to treat like with like and use a inc/dec counter:

mob
    var
        nomove = 0
    Move()
        if(nomove) return 0
        . = ..()
    proc
        stun(duration)
            ++nomove
            sleep(duration)
            if(--nomove<0) nomove = 0


In this case, all of these status effects did the exact same thing. This comes with the additional bugfix where a boolean can't necessarily be reset by a reapplication of the same status effect, effectively ending a prior or longer stun prematurely, or even causing all kinds of hidden bugs and corner cases.

Booleans in BYOND are probably worse than in just about any other language, TBH. A single boolean value is about 39 wasted bits of memory minimum, whereas in any other language, they are between 0 wasted bits and 7 wasted bits. A few languages do align co-defined booleans into a single memory region during compilation (which is why class-structuring in C++ is so damn important to understand), but not many of them do.

Booleans are one of those things that I find it's best to get out of the habit of pretty fast, because, well, reasons that only become apparent later.
Feb 5 2016, 6:47 pm
it honestly isn't bools, we tend to bitflag those, (with a few cases of items or objects doing "can_do_something = 0 spawn(timer) can_do_something = 1" where that something changes per item and couldn't be generalized to the root status flags all objects/items have.

its everything else, usually per type things that don't change per item in the type much
Feb 5 2016, 7:00 pm
its everything else, usually per type things that don't change per item in the type much

Ah, is that what you were researching the static flag for the other day? I think I'm getting a glimpse of your wheels turning.
Feb 6 2016, 1:19 pm
Well, no, just about everything that never changes per type is static.

Its things that rarely change per type that become the issue. name and desc are some examples, they are almost always the same per type, except when they aren't.

Health for most of the things doesn't change much, but thats per item.

Another example is vars that do change, but on objs that aren't active. We stuff build components inside of the completed form to save on New() costs during deconstruction, mainly mass deconstruction, like a black hole or explosion ripping something apart.

Or items that turn into objs on construction, like pipes, the version you can hold is a subtype of /obj/item (/obj/item is anything you can hold) but the wrenched in version isn't an item/ so it has a different path, we stuff the pipe used to build it inside of it so it can be spat out on deconstruction.

There are also the high level vars that aren't used in most subtypes, and should really be lower in the type tree, and replaced with a proc call/oop setup, but proc call overhead.

/obj has 117 vars

/turf/space, the most basic turf type that i can spawn, has 93 vars

/mob/ has 218 vars

Some of those could be moved to be higher in the tree, and/or replaced with oop procs that return null on the base type, but proc call overhead is a concern for some, and the work of investigating the others that were from before we had standards is hard and not something many people would be motivated to do.
Feb 7 2016, 1:42 pm
In response to Ter13
Booleans are typically stored as bytes because it is -MUCH- faster to evaluate bytes than it is to evaluate bitflags. They're much preferable to use for things you'll be reading a lot of. However, in BYOND, they are stored as 32 bits since byond doesn't have different integer types. Bitflags would still technically be slower to read/write, but they are saving much more space.
:the more you know:
Feb 7 2016, 9:48 pm
In response to Somepotato
Somepotato wrote:
Booleans are typically stored as bytes because it is -MUCH- faster to evaluate bytes than it is to evaluate bitflags. They're much preferable to use for things you'll be reading a lot of. However, in BYOND, they are stored as 32 bits since byond doesn't have different integer types. Bitflags would still technically be slower to read/write, but they are saving much more space.
:the more you know:

They're actually stored as 64 bits. The Value struct is 40 bits and pads out to 64.
Feb 7 2016, 9:50 pm
In response to Lummox JR
Didn't consider the value struct.
YOU HEARD IT HERE FIRST FOLKS, USE BITFLAGS!
Apr 1 2016, 5:50 pm
Bumping this to remind lummox to get it in since he's talking about "getting closer to a stable release of 510"
Apr 15 2016, 7:15 pm
alrighty now, since we are looking at this waiting for 511, i wanted to pitch an idea that would require changing the compile format of the dmb.


What if objects had a simple jump table pointing to the location of vars in the changed list or initial list.

It would still be a massive increase in memory but you could make that much smaller by limiting this to Objects/datums with 255 or less variables, and making it an array of unsigned char, where the array values are indexes to the changed vars array with some magic number meaning that var isn't in the changed var array.

Why do that? So you can compile in array indexes for datum vars like you do global vars and world vars and proc vars of course!

This could lead to a MASSIVE improvement in runtime speed.

To reiterate, datums would have:

1 global per type array of vars info including the default initial() value and other metadata.

1 per instance jump table like parallel array of shorts or bytes that point to the index of the var in the changed var list with a magic number indicating that var hasn't been changed, and to look in the initial() list above for the var at the same index.

1 per instance array of changed variables (currently a linked list)

If the first two lists share indexes, (are parallel) you could compile in var indexes for properly typed accesses, and revert to old behavior for : or side typing (where a var is typed as /datum/a, but holds a /datum/b, but they both have the right var even thou /datum/ doesn't have that var (ie, they both define the same var name)).

Apr 15 2016, 10:12 pm
In response to MrStonedOne
I'm not sure that approach would be feasible. For starters, whether a datum has less than 255 vars is hard to figure out at compile-time; the current tree-flattening is being done at runtime. Also, compiling vars as array indices would effectively require that the language become hard-typed, because a reference to item._arrayvars[43] would mean something completely different if the item were the wrong type.

Basically the core problem is that datum vars are never resolved until a read/write happens, so that the language can be loosely typed. Resolving them at compile-time is not compatible with the language structure.
Apr 16 2016, 4:25 am
Why not both, resolve at compile time, fall back to old behavior at runtime if there is a mismatch
Apr 16 2016, 2:05 pm
That would be impossible. Resolving at compile-time just won't work.
Jun 23 2016, 9:59 am
The optimization is in place for 511, after much head-scratching trying to pin down a problem, and I'm going to run some tests on SotS II to see how it compares to the old way. My guess is that the results are going to be inconclusive, and we may have to see in production what actual effect this has. I did add a minor optimization in the new var type that includes the name reference directly, which should avoid name lookups and hopefully offer at least a minor speed boost on its own.
Jun 23 2016, 2:16 pm
As expected, my results are extremely murky. However, it's possible results will differ on other processors, so I'll leave this in and see how the first 511 release shakes out.
Jun 25 2016, 4:56 pm
Oddly enough, by now we redesigned how atmos works to lower on its overhead in a way that will make this not affect it as much. (basically, everything is now stored as members of a statically keyed list)

Mob processing how ever will see massive improvement, 300 to 500 vars (depending on what mob) processed across like 50 procs, for each mob every 2 seconds.

That being said once 511 is out I'll profile this across all of our stuff and get back

Hey maybe for 512 we'll get inline procs and vars and kill off even a bit more overhead =P

Anywho, hopefully a server cpu with its bigger and faster cache will show more improvement.
Jul 2 2016, 1:23 pm
Out of curiosity, what does the implementation look like? is it an array of pointers to structs, or an array of structs?

Jul 2 2016, 2:04 pm
It's an array of structs. The string ID is stored in this new struct for ease of comparison, because the array is sorted in string ID order.
Jul 2 2016, 2:32 pm
oh.... so binary search?
Page: 1 2 3 4