News:

The Forum Rules and Guidelines
Our forum has Rules and Guidelines. Please, be kind and read them ;).

[PATCH] Sort suppliers and lieferziele by distance from factory

Started by ansgar, February 05, 2009, 06:53:52 PM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

ansgar

Hi,

In the factory info dialog, the list of suppliers and consumers is currently unsorted.  I often want to connect factories to the nearest supplier/consumer, but I have to find this currently by hand.  So I prepared a patch to make Simutrans do this instead :-)

The attached patch (0002-Sort-lieferziele-and-suppliers-by-distance-from-this.patch) makes Simutrans sort the list of suppliers and consumers by distance from the factory.

The other patch (0001-Add-const-qualifier-to-abs_distance.patch) just adds a const qualifier to the parameters of abs_distance and passes the parameters by-reference instead of by-value.

Ansgar

prissi

Unfortunately beos has not std:stable_sort.

Furthermore, if we add something to the array, we could simply add it to the correct position anyway. Adding and then sorting is not a very clever choice (although is does not matter, as we call this very rarely).

In trunk anyway.

ansgar

I think the code is more readable if the logic for this is moved to `vector_tpl' instead of fabrik_t itself.  Also it may be reusable in other places this way.  See the attached patch.

Ansgar

prissi

Could you elaborate a little on why this works?

StrictWeakOrdering is nowhere defined?! I am not against inclusion, but this is imho a nice example how C++ can be used to produce code that is very hard to understand. (Especially overloading () is kind of evil, since it break normal expectations.)

ansgar

StrictWeakOrdering is a template parameter, so it does not need to be defined.  It is instanced with RelativeDistanceOrdering in the case.

Sorting requires a comparison function, but here we need a different sorting function for each fabrik_t object.  In C++ this can be implemented with "function objects", that is objects that actually behave like a function by overloading the () operator.  I find it easier to think of function objects just like regular functions (if you do this, overloading the () operator is also not so confusing any more).

In C you would pass a function pointer instead, but in this case you would have to pass a third argument to the function so you can pass the "origin" coordinate (usually you would pass a void* parameter).  Function objects "hide" this by encapsulating this information in the object, which I think is more elegant.

Function objects are used in many places in the C++ Template Library: all functions from <algorithm> are intended to be used with function objects (at least where it makes sense).  For example std::sort can either use the < operator or a function object (see [1]).  Note that any normal function is also a function object.

SGI's documentation also has a chapter dedicated to function objects[2].

Ansgar

[1] http://www.sgi.com/tech/stl/sort.html
[2] http://www.sgi.com/tech/stl/functors.html

prissi

Well I get the idea, and I like it to be reusable in vector_tpl. But I have to disagree on the readability.

The way with this function objects is hiding of functionality at unexpected places. This is one of the worst features of C++, imho, overloading things with stuff that is not expected. Maybe I am not a C++ guy then, but for me this results in code very hard to be understood, compared to the while loop at the add_lieferziel.

Maybe I am just too old then.

jamespetts

Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

ansgar

I disagree with your disagreement ;-)  Reading insert_ordered(...) is easier (for me) than guessing what the for-loop is intended to do exactly.  But in the end you decide what ends up in the simutrans code :-)

I just want to point out that the same method is already used in several other places:

% git grep 'operator ()'
gui/citylist_stats_t.cc:                bool operator ()(const stadt_t* a, const stadt_t* b)
gui/curiositylist_stats_t.cc:           bool operator ()(const gebaeude_t* a, const gebaeude_t* b)
gui/factorylist_stats_t.cc:             bool operator ()(const fabrik_t* a, const fabrik_t* b)
gui/labellist_stats_t.cc:               bool operator ()(const koord a, const koord b)


and used for std::sort.

As we are already talking about readability:  I noticed simutrans has constructs like this

       // only this works with O3 optimisation!
       return ((a.x-b.x)|(a.y-b.y))==0;

instead of the (more readable)

       return (a.x == b.x) && (a.y == b.y);

which also should work with any optimization setting.  Is there any reason to prefer the first version?  I doubt it makes much of a difference performance-wise (actually I would assume integer arithmetic to be slower than equality tests).  But the main point is that I think readability is more important than a few CPU cycles in most cases.

Also, is there any special reason behind using vector_tpl instead of std::vector?  std::vector should be supported everywhere by now.

Ansgar

VS

You don't want to dispute prissi's optimizations ;D He will bring some obscure reason like pipelining and will be right.

My projects... Tools for messing with Simutrans graphics. Graphic archive - templates and some other stuff for painters. Development logs for most recent information on what is going on. And of course pak128!

ansgar

It may be faster or slower, but that's not my point.

I think it is harder to read and that this is (at least in most cases) more important than a few CPU cycles.

Ansgar

VS

Well, that might or might not be true. You might not want to make assumptions about such widely used objects as koords...

My projects... Tools for messing with Simutrans graphics. Graphic archive - templates and some other stuff for painters. Development logs for most recent information on what is going on. And of course pak128!

jamespetts

Quote from: VS on February 06, 2009, 03:43:52 PM
You don't want to dispute prissi's optimizations ;D He will bring some obscure reason like pipelining and will be right.

Au contrere, please do: I'll learn a great deal about coding and Simutrans if Ansgar and Prissi have a long debate ;-)
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

Spike

I'm also interested in why Prissi's version is performing better than Ansgar's suggestion. The only real difference that I can spot is that Ansgar's version triggers short circuit evaluation, which usually is a good thing, though (once known that a.x is not equal b.x the rest of the term does not need to be evaluated). It might be less efficient with pipelines, though, that's why I'm curious about Prissi's answer to this :)

prissi

[offtopic]
All the stuff with std:: was brough in later by tron. I did not like it, since it somehow breaks the simutrans templates. But he did not like them just because std:: is there. However, in the end I had to sped a week to get the code compiling again on BeOS which uses NOT GCC.

Tron hosts the svn and has write access. Thus he checked it in and I was too tired to discuss. Before him, vector_tpl and slist_tpl were identical (apart from the iterator). I think I will restore the standard simutrans names like get_count() and is_empty() and is_contained() for all simutrans templates. The names in std:: are imho not very helpful, if you never heard of std:: (as I did, because it was not invented yet, when I had my IT for scientist classes.)
[/offtopic]

On readability: The comparison of koordinates is one of the major eater of calculation time (albeit at total on 1.1% of all time). (a.x==b.x  &&  a.y==b.y) is slower, since it has a conditional which usually invalides the pipe. The additional comparisons are more or less three circles, which outweigth the stall at jump more or less. However, I need to test this again, as processors have become smarter. (Before there was *(uint32)&a==*(uint32)&b, which did not work out with O3 optimisations and was not to the liking of some compiler). At some point however, there was a more elaborate comment.

But ontopic. I was too tired and I admid that putting the class into the array is the best way, since it also allows to acess members without range check. My only comment is, that such a class should go to koord, after some thinking.

I am sorry, I should not post when I am too tired.

Spike

Quote from: prissi on February 06, 2009, 07:05:47 PM
(Before there was *(uint32)&a==*(uint32)&b, which did not work out with O3 optimisations and was not to the liking of some compiler).

That seems like my way to optimize stuff  ;) Yes, was an ugly hack trying to force comparison by only one operation. Definitely on the borderline of safe coding, but supposedly quick ::)

whoami

Quote from: prissi on February 06, 2009, 07:05:47 PM
On readability: The comparison of koordinates is one of the major eater of calculation time (albeit at total on 1.1% of all time).
For readability and easier maintenance, shouldn't checks like this be done by a macro or inline function?

Quote(a.x==b.x  &&  a.y==b.y) is slower, since it has a conditional which usually invalides the pipe.
This should result in a conditional jump forward, and the CPU should cope by discarding only the result of the next comparation (which would be executed speculatively, in parallel). (But I don't know which CPU generations can handle it this way, or which optimization settings are necessary.)
The current check (ansgar's post) has two subtractions, and a bit-wise or which depends on both, so that parallelization can't happen, except if the compiler understands that the '== 0' can be distributed to the operands of the '|'.

prissi

Since compare does just a substraction and discards the result, comp and sub have the same speed; sometime sub is eve faster (like on 68000 in some situations). The substraction could be in principle done in parallel, only the or has to be done after. But all those can be pipelined, while a jump cannot be pipelined. But I will do profiling again on my new machine.