Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[devek]

That is pretty awesome, for looking at the macro sense of things. I like the graph too about memory vs cpu, which is something I have been harping on for years been never had a visual way to explain.

For the micro stuff, I always refer people to the books at http://www.agner.org/optimize/

[Veroule]

I think a few of us should point that pdf out to Toady, since it is very likely to be the easiest to implement large scale optomization for DF.  We just have to figure out the best tool and method for diagnosing where to make such an optomization.

Devek, thanks for the link to agner.  I hadn't found that one yet and it looks like the information there might just teach me a few new tricks.  I firmly believe in the saying, "You can't teach an old dog new tricks."  Learning new things is the only way to stay young.

[G-Flex]

I think a few of us should point that pdf out to Toady, since it is very likely to be the easiest to implement large scale optomization for DF.

Not a bad idea, but I think there are bigger fish to fry. I'd rather he spend time learning about software development in general before worrying about obscure optimization techniques.

[devek]

Not a bad idea, but I think there are bigger fish to fry. I'd rather he spend time learning about software development in general before worrying about obscure optimization techniques.

There is nothing obscure about it.

Like the document says, what can you do in 400 cycles?

Take a fort with 10,000 items. Each item is an object that takes around 120 bytes. The items are on a C++ heap, which means they are randomly spaced out and can be in any order imaginable. So you dwarf decides to go make a table and needs to find some wood. It needs to scan through every single item to find out what is wood, and what is close. The memory access alone will take close to 4,000,000 memory cycles.

This is why, to the original point of this thread.. it wouldn't matter the code to access an item was written in assembly, java, or anything else. The vast majority of time in execution is the processor waiting on memory.

There are many ways to fix the problem. I could do a drop replacement of the the stl vector class that to group items in contiguous memory that would shave MILLIONS of cpu cycles off. I could put all the items in a r-tree, and it would still save millions of cycles.

[ZCM]

Not a bad idea, but I think there are bigger fish to fry. I'd rather he spend time learning about software development in general before worrying about obscure optimization techniques.

There is nothing obscure about it.

Like the document says, what can you do in 400 cycles?

Take a fort with 10,000 items. Each item is an object that takes around 120 bytes. The items are on a C++ heap, which means they are randomly spaced out and can be in any order imaginable. So you dwarf decides to go make a table and needs to find some wood. It needs to scan through every single item to find out what is wood, and what is close. The memory access alone will take close to 4,000,000 memory cycles.

This is why, to the original point of this thread.. it wouldn't matter the code to access an item was written in assembly, java, or anything else. The vast majority of time in execution is the processor waiting on memory.

There are many ways to fix the problem. I could do a drop replacement of the the stl vector class that to group items in contiguous memory that would shave MILLIONS of cpu cycles off. I could put all the items in a r-tree, and it would still save millions of cycles.

I would build auxilliary lists for just wood, just stone, etc., avoiding the need to scan through every single item in the first place.

[Thief^]

I would build auxilliary lists for just wood, just stone, etc., avoiding the need to scan through every single item in the first place.

I would make a way to assign a stockpile to a workshop. That way you only need to check the contents of the stockpile, instead of every item in the whole game...

[vlademir1]

Perhaps not 100% what you were looking for, but I found this nice.

Thank you.  That was a very interesting, and potentially useful, document.

I would make a way to assign a stockpile to a workshop. That way you only need to check the contents of the stockpile, instead of every item in the whole game...

The stockpile itself would still have to look through everything, and every removal adds a new job to the stack once it's full so it has to do all that again and again for each job item removed.

The following reply ties into the one above.

I would build auxilliary lists for just wood, just stone, etc., avoiding the need to scan through every single item in the first place.

Really those should be lists of lists, one list for each stockpile category pointing to lists of items.  The problem is made more complex by the way quality and material affect things. So a Furniture list (as an example) points to bed, barrel, bin, anvil, etc lists which in turn point to lists of those items by quality and material which point to the individual items with that quality and material (masterwork tin barrel list, fine tin barrel list, etc). 

My guess is that is a big bottleneck in DF FPS like pathfinding.  Every not full stockpile searching the items and adding jobs for those items matching it's criteria to be brought to that stockpile, likely with a lot of nested conditionals.

[Thief^]

I would make a way to assign a stockpile to a workshop. That way you only need to check the contents of the stockpile, instead of every item in the whole game...

The stockpile itself would still have to look through everything, and every removal adds a new job to the stack once it's full so it has to do all that again and again for each job item removed.

Considering people use stockpiles for workshops anyway, most of those downsides already exist. Assuming some way of iterating through the contents of a stockpile without iterating every item and doing an "are you in this stockpile" check, it would be more efficient to have the game know that a particular stockpile is intended for a particular workshop. It would also allow workshops to be restricted on the materials they could use, and would fix the bug of dwarves sometimes grabbing rocks from random places (closest to where they happen to be at the time?) instead of from the stockpile closest to the workshop. Wins all round.

[devek]

I don't know how much that would help as much as it would move the problem, either way it would be a cool feature.. here is another example.

Lets talk about designations.

The current map I am on is 100 z levels, and 192x192 tiles for each z level. The game divides those into map blocks which are 16x16. So that means there are 14,400 map blocks on my map(on a very fragmented heap). The designation status for each map block is stored in a 32 bit int, which is in an array of contiguous memory (1024 bytes). That means there are 14,745,600 bytes of storage just for designations alone.

When you designate a tile to be dug, it marks the map block as "dirty" and updates the designation.

Thanks to the dirty bit, the game doesn't have to read through all 14,745,600 bytes each game frame... but it still needs to check each map block(with scattered reads) if it is dirty. So there are about 5,760,000 clock cycles spent each frame checking to see if you are trying to cut down a tree or something regardless of if you are.

I could go on like this all day. But knowing as much as I do about DF, it kind of cracks me up when people talk about how DF should be threaded.. or it should use this different pathingfinding trick or w/e. They have no idea what the real problems are.

[Thief^]

Thanks to the dirty bit, the game doesn't have to read through all 14,745,600 bytes each game frame... but it still needs to check each map block(with scattered reads) if it is dirty. So there are about 5,760,000 clock cycles spent each frame checking to see if you are trying to cut down a tree or something regardless of if you are.

If that is accurate, that is about 20% of an ideal 100fps frame! That's insane.

[qwertyuiopas]

When pathfinding to a task(construction, mining, etc.), rather than path to each of the 8 directions, why not path to the tile itself(temporarily marking it as passable, if required) and then stop one tile short?

Also, pathfinding will remain a huge issue for the exact same reason that you propose it isn't: Exactly how many times will it need to retrieve data about the terrain? Reducing the excess sprawl of the pathfinding would reduce cache misses thus, if I understand correctly, leaving more cache for other things.

[devek]

You hit the nail on the head more or less.

I'm not saying the pathfinding function is good or bad. I am just saying that with the available data, any pathfinding function would be slow. The function isn't the problem.

[darius]

Not a bad idea, but I think there are bigger fish to fry. I'd rather he spend time learning about software development in general before worrying about obscure optimization techniques.

There is nothing obscure about it.

Like the document says, what can you do in 400 cycles?

Take a fort with 10,000 items. Each item is an object that takes around 120 bytes. The items are on a C++ heap, which means they are randomly spaced out and can be in any order imaginable. So you dwarf decides to go make a table and needs to find some wood. It needs to scan through every single item to find out what is wood, and what is close. The memory access alone will take close to 4,000,000 memory cycles.

This is why, to the original point of this thread.. it wouldn't matter the code to access an item was written in assembly, java, or anything else. The vast majority of time in execution is the processor waiting on memory.

There are many ways to fix the problem. I could do a drop replacement of the the stl vector class that to group items in contiguous memory that would shave MILLIONS of cpu cycles off. I could put all the items in a r-tree, and it would still save millions of cycles.

I would build auxilliary lists for just wood, just stone, etc., avoiding the need to scan through every single item in the first place.

It is already done like that by df (AFAIK)

[Thief^]

Actually, it seems like same-Z-level pathfinding performance would be pretty good. Pathfinding up/down would cache miss every tile though, and pathfinding across the data layout (probably Y) wouldn't be much better...

So there we go, for performance design forts so that most dwarf movement is east/west

[devek]

It is already done like that by df (AFAIK)

I'm not saying at an auxiliary list would be the way to go, but I can say with 100% certainty that there are none. If they existed, writing dwarf foreman would be a lot simpler. There are different classes for each item, and those items are stored in a polymorphic way in a vector. You still have to iterate through every single item and implement a series of switch statements to actually figure out what an item is.

This is a snippet of the exact decompiled DF code when it is looking for an item..

Spoiler (click to show/hide)

Code: [Select]

    switch( itemType )
    {
    case 0: // block or bar
        if ( materialIndex )
        {
            if ( materialIndex == 7 )
            {
                if ( materialSubIndex == 1 )
                {
                    return "charcoal";
                }
                else
                {
                    if ( materialSubIndex )
                        return "refined coal";
                    else
                        return "coke";
                }
            }
            else
            {
                if ( materialIndex == -1 )
                {
                    return "bars";
                }
                else // for stuff like potash and ash
                {
                    return itemMaterial(materialIndex, materialSubIndex, 0, 0);
                }
            }
        }
        else
        {
            if ( materialSubIndex == 25 )
                return itemMaterial(0, materialSubIndex, 0, 0) + " wafers";
            else
                return itemMaterial(0, materialSubIndex, 0, 0) + " bars";
        }
        break;

    case 1: // cut gems
        if ( materialIndex == 3 ) return "cut green glass gems";
        if ( materialIndex == 4 ) return "cut clear glass gems";
        if ( materialIndex == 5 ) return "cut crystal glass gems";
        if ( materialIndex == -1 ) return "cut gems";
        if ( materialSubIndex == -1 ) return "gems";
        return gemMaterial(materialIndex, materialSubIndex, 1);