Print

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

[SolarShado]

I doubt there's a "number of rocks" variable that has a direct influence on much of anything. Rocks aren't just a number, they have all kinds of properties - location, material, forbidden, hidden, marked for dumping, hauled by someone, melting point, weight, etc etc etc. Those properties have to be stored in some kind of structure, so rocks can't just be stored in an integer. Probably the only thing you'd screw up is the UI trying to display the number of rocks.

Like an array? whose max size (AFAIK) is an integer?
But then there is this:

It could use a linked list, or a doubly linked list, or some variant, as that would allow unlimited objects and easy removal and addition of them, although searching might be a bit slow, so it probably has some sorting mechanism...

I hadn't thought about that myself. I'd say it's safe to assume there's a sorting algorhythm(sp), but i'd guess it only runs when you happen accross the stone menu.

[GenericOverusedName]

Huh, what about vectors? Ahyuck! (I hate vectors).

Which brings up the question... what language is DF written in anyways? It probably wouldn't affect this experiment much, but I'm just curious.

[Baboonanza]

C++, using the standard template library I believe. From reading the assembly I know how constructions work and although I haven't checked that all of this applies to objects I would expect it to be very similar/identical in approach:

Objects/Constructions are heap allocated and pointers are stored in a std::vector (there may be an additional two for sub-categories, I'm not quite sure), which allows polymorphism. They are sorted  position (x-y-z). Searching by position uses a Binary Search (http://en.wikipedia.org/wiki/Binary_search). This means inserting/removing objects can be slow due to vector copying chunks of memory about but searching is very quick, which is what you would expect.

I'm not quite sure why accessing the stocks list can be so slow. Even though it must have to scan all of the objects and allocate memory for storing results it seems slower than it should be. It's possible that it's just poorly optimized, or that there is some hidden complexity I'm missing.

Edit: Got the sortng wrong. Corrected.

[Draco18s]

I'm not quite sure why accessing the stocks list can be so slow. Even though it must have to scan all of the objects and allocate memory for storing results it seems slower than it should be. It's possible that it's just poorly optimized, or that there is some hidden complexity I'm missing.

Because it's counting.

129,000 Limestone
38,000 Granite
42,317 Shale
128,452 Sandstone
...

[Corona688]

You'd be surprised... Checking for overflow is non-trivial and would introduce a branch, which can be disastrous if you care about performance. If you're lucky the compiler will optimize it, but I usually leave any checks out in a release build and pray/check the math that it can't happen instead. Meaning, if you do have the patience to generate that many rocks you'll probably run into undefined behaviour, which might not make it crash. It could potentially do anything. Most compilers these days handle it rather gracefully by just wrapping to zero, however.

In any architecture I know of overflows always wrap from maximum to zero for unsigned, or maximum to negative maximum for unsigned, because of the way binary integers work.

[Xinael]

He's not talking about filling up an integer, because integers don't have much to do with anything. He's talking about a rather worse kind.

[Baboonanza]

Because it's counting.

129,000 Limestone
38,000 Granite
42,317 Shale
128,452 Sandstone
...

You know what computers are really, really good at? Counting My point is that given my understanding of how it works it takes an order of magnitude longer than I would expect it too. So either it's doing something much more complicated than I expect or it's implemented poorly.

My guess would be that there is no differentiation in the code between the complex objects such as clothing which are difficult to collate into a grouped list and the simple objects like blocks and rocks. The latter are larger in number but easier to collate and would benefit substantially from an optimised (and easy/quick to code incidentally) counting method. I could be completely wrong but given Toady generally seems to know what he's doing algorithmically this seems more likely than it just being poorly written.

[Draco18s]

Because it's counting.

129,000 Limestone
38,000 Granite
42,317 Shale
128,452 Sandstone
...

You know what computers are really, really good at? Counting My point is that given my understanding of how it works it takes an order of magnitude longer than I would expect it too. So either it's doing something much more complicated than I expect or it's implemented poorly.

It's doing more.  When you look at the stone list it does display some other data (such as forbidden status) and the like.  Because it doesn't take an age and a day to switched views (tab) I suspect that it's making the huger list first, then counting.

[Corona688]

You know what computers are really, really good at? Counting My point is that given my understanding of how it works it takes an order of magnitude longer than I would expect it too. So either it's doing something much more complicated than I expect or it's implemented poorly.

It's more complicated than you expect.  Remember there's a record keeper involved, it has to keep in mind how accurate its supposed to be and whether the record keeper has tallied it yet...