[PATCH] Sort suppliers and lieferziele by distance from factory

Topic: [PATCH] Sort suppliers and lieferziele by distance from factory (Read 8750 times) previous topic - next topic

[PATCH] Sort suppliers and lieferziele by distance from factory

February 05, 2009, 06:53:52 pm

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 p****es the parameters by-reference instead of by-value.

Ansgar

Re: [PATCH] Sort suppliers and lieferziele by distance from factory

Reply #1 – February 05, 2009, 09:33:42 pm

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.

Re: [PATCH] Sort suppliers and lieferziele by distance from factory

Reply #2 – February 05, 2009, 11:32:53 pm

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

Re: [PATCH] Sort suppliers and lieferziele by distance from factory

Reply #3 – February 06, 2009, 11:32:22 am

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.)

Re: [PATCH] Sort suppliers and lieferziele by distance from factory

Reply #4 – February 06, 2009, 12:19:27 pm

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 p**** a function pointer instead, but in this case you would have to p**** a third argument to the function so you can p**** the "origin" coordinate (usually you would p**** 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

Re: [PATCH] Sort suppliers and lieferziele by distance from factory

Reply #5 – February 06, 2009, 02:11:28 pm

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.

Re: [PATCH] Sort suppliers and lieferziele by distance from factory

Reply #6 – February 06, 2009, 03:28:39 pm

Well, I prefer C#... ;-)

Re: [PATCH] Sort suppliers and lieferziele by distance from factory

Reply #7 – February 06, 2009, 03:37:49 pm

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:

Code: [Select]

% 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

Code: [Select]

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

instead of the (more readable)

Code: [Select]

        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 ****ume 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

Re: [PATCH] Sort suppliers and lieferziele by distance from factory

Reply #8 – February 06, 2009, 03:43:52 pm

You don't want to dispute prissi's optimizations

He will bring some obscure reason like pipelining and will be right.

Re: [PATCH] Sort suppliers and lieferziele by distance from factory

Reply #9 – February 06, 2009, 04:00:15 pm

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

Re: [PATCH] Sort suppliers and lieferziele by distance from factory

Reply #10 – February 06, 2009, 04:18:41 pm

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

Re: [PATCH] Sort suppliers and lieferziele by distance from factory

Reply #11 – February 06, 2009, 04:37:31 pm

Quote from: VS – on February 06, 2009, 03:43:52 pm

You don't want to dispute prissi's optimizations 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 ;-)

Re: [PATCH] Sort suppliers and lieferziele by distance from factory

Reply #12 – February 06, 2009, 04:43:28 pm

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

Re: [PATCH] Sort suppliers and lieferziele by distance from factory

Reply #13 – February 06, 2009, 07:05:47 pm

[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 cl****es.)
[/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 cl**** into the array is the best way, since it also allows to acess members without range check. My only comment is, that such a cl**** should go to koord, after some thinking.

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

Re: [PATCH] Sort suppliers and lieferziele by distance from factory

Reply #14 – February 06, 2009, 08:44:35 pm

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

Re: [PATCH] Sort suppliers and lieferziele by distance from factory

Reply #15 – February 07, 2009, 04:13:18 am

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 '|'.

Re: [PATCH] Sort suppliers and lieferziele by distance from factory

Reply #16 – February 07, 2009, 07:45:17 pm

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.