Move time and compiler optimization

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Edmund
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

Move time and compiler optimization

Post by Edmund » Sun Mar 23, 2014 1:40 pm

When the engine receives the go command, it stores the current system time, then it starts the search and every certain number of nodes it checks whether the (current system time) - (initial system time) > (maximum move time). I need the current system time to be as accurate as possible to keep safety time buffers as small as possible and also not risk running out of time.

I would have something like:

Code: Select all

blocked wait for message
if (message == go) intial_time = system_time();
Now I wonder whether there exists the risk of compilers reordering instructions; and if so, what can we do about this.

scenario 1:

Code: Select all

r1 = system_time();
blocked wait for message
if (message == go) intial_time = r1;
scenario 2:

Code: Select all

blocked wait for message
<do other stuff here>
if &#40;message == go&#41; intial_time = system_time&#40;);

User avatar
hgm
Posts: 23008
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Move time and compiler optimization

Post by hgm » Sun Mar 23, 2014 3:19 pm

Scenario 1 is certainly impossible. In scenario 2 it coulld never do something significant before reading the clock, like a function call. A compiler cannot reorder functions when it doesn't know what they do.

Daniel Shawul
Posts: 3572
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Move time and compiler optimization

Post by Daniel Shawul » Sun Mar 23, 2014 3:29 pm

Hi Edmund I don't think compilers will reorder instructions that will break code in an obvious way such as this one. Out of order execution is used to avoid pipeline stalls due to data unavailability. A single line of code (e.g x++) is broken down to many instructions on which pipelining and reordering occurs, not at a larger scale that will re-order system-time call with wait_for_messages.
But my knowlege about the topic is limite.

syzygy
Posts: 4376
Joined: Tue Feb 28, 2012 10:56 pm

Re: Move time and compiler optimization

Post by syzygy » Sun Mar 23, 2014 4:10 pm

Both receiving I/O and reading system_time involve side effects. A compiler is not allowed to reorder side effects across sequence points. There are sequence points between "blocked wait for message" and the evaluation of "message == go" and between the evaluation of "message == go" and "inital_time = system_time()".

So scenario 1 is impossible.

Scenario 2 is possible in so far as the compiler can determine that "other stuff" has no side effects.

mar
Posts: 1919
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Move time and compiler optimization

Post by mar » Sun Mar 23, 2014 4:57 pm

Hello Edmund,
as far as I know function calls (whether inline or not) are sequence points (as defined by the standard) so I wouldn't worry there (plus arguments are guaranteed to be evaluated before function body is entered).

A real-life example that happened to me some time ago:

Code: Select all

    	nodes&#91;res&#93;.index = addNode&#40; n->front );
where nodes is a vector that can be changed by subsequent call to recursive method addNode.
What happened is that the compiler cached pointer to nodes before calling addNode which pushes back some elements (sure I might have preallocated nodes in advance by using pre-traversal).
It's because the order of evaluation of assignment operator is not guaranteed (it's not a sequence point unlike && and || operators which are guaranteed to evaluate left to right),
so the compiler is free to evaluate left side first (read where to store the result, not the store itself).

Fixing it was simple enough:

Code: Select all

        int tmp = addNode&#40; n->front );
        nodes&#91;res&#93;.index = tmp;
One has to be careful sometimes :)
From what I've read sequence points are also automatically "inserted" at the end of each expression statement.

Hope it helps.

bob
Posts: 20358
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Move time and compiler optimization

Post by bob » Mon Mar 24, 2014 1:58 am

mar wrote:Hello Edmund,
as far as I know function calls (whether inline or not) are sequence points (as defined by the standard) so I wouldn't worry there (plus arguments are guaranteed to be evaluated before function body is entered).

A real-life example that happened to me some time ago:

Code: Select all

    	nodes&#91;res&#93;.index = addNode&#40; n->front );
where nodes is a vector that can be changed by subsequent call to recursive method addNode.
What happened is that the compiler cached pointer to nodes before calling addNode which pushes back some elements (sure I might have preallocated nodes in advance by using pre-traversal).
It's because the order of evaluation of assignment operator is not guaranteed (it's not a sequence point unlike && and || operators which are guaranteed to evaluate left to right),
so the compiler is free to evaluate left side first (read where to store the result, not the store itself).

Fixing it was simple enough:

Code: Select all

        int tmp = addNode&#40; n->front );
        nodes&#91;res&#93;.index = tmp;
One has to be careful sometimes :)
From what I've read sequence points are also automatically "inserted" at the end of each expression statement.

Hope it helps.
That statement leaves a lot to be desired. "each expression statement" means what when a compiler has taken the instructions from several consecutive source statements and interlaced them like a drunken programmer? The concept "sequence point" is extremely vague when you get down to actual programming and the compiler. Fortunately an accurate data flow graph (which any optimizing compiler produces as a natural work product) takes care of this funny stuff.

syzygy
Posts: 4376
Joined: Tue Feb 28, 2012 10:56 pm

Re: Move time and compiler optimization

Post by syzygy » Mon Mar 24, 2014 9:04 am

bob wrote:
mar wrote:Hello Edmund,
as far as I know function calls (whether inline or not) are sequence points (as defined by the standard) so I wouldn't worry there (plus arguments are guaranteed to be evaluated before function body is entered).

A real-life example that happened to me some time ago:

Code: Select all

    	nodes&#91;res&#93;.index = addNode&#40; n->front );
where nodes is a vector that can be changed by subsequent call to recursive method addNode.
What happened is that the compiler cached pointer to nodes before calling addNode which pushes back some elements (sure I might have preallocated nodes in advance by using pre-traversal).
It's because the order of evaluation of assignment operator is not guaranteed (it's not a sequence point unlike && and || operators which are guaranteed to evaluate left to right),
so the compiler is free to evaluate left side first (read where to store the result, not the store itself).

Fixing it was simple enough:

Code: Select all

        int tmp = addNode&#40; n->front );
        nodes&#91;res&#93;.index = tmp;
One has to be careful sometimes :)
From what I've read sequence points are also automatically "inserted" at the end of each expression statement.

Hope it helps.
That statement leaves a lot to be desired. "each expression statement" means what when a compiler has taken the instructions from several consecutive source statements and interlaced them like a drunken programmer? The concept "sequence point" is extremely vague when you get down to actual programming and the compiler. Fortunately an accurate data flow graph (which any optimizing compiler produces as a natural work product) takes care of this funny stuff.
You do not have to show that you have no clue about the C standard.

AlvaroBegue
Posts: 913
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: Move time and compiler optimization

Post by AlvaroBegue » Mon Mar 24, 2014 11:56 am

bob wrote:
mar wrote:Hello Edmund,
as far as I know function calls (whether inline or not) are sequence points (as defined by the standard) so I wouldn't worry there (plus arguments are guaranteed to be evaluated before function body is entered).

A real-life example that happened to me some time ago:

Code: Select all

    	nodes&#91;res&#93;.index = addNode&#40; n->front );
where nodes is a vector that can be changed by subsequent call to recursive method addNode.
What happened is that the compiler cached pointer to nodes before calling addNode which pushes back some elements (sure I might have preallocated nodes in advance by using pre-traversal).
It's because the order of evaluation of assignment operator is not guaranteed (it's not a sequence point unlike && and || operators which are guaranteed to evaluate left to right),
so the compiler is free to evaluate left side first (read where to store the result, not the store itself).

Fixing it was simple enough:

Code: Select all

        int tmp = addNode&#40; n->front );
        nodes&#91;res&#93;.index = tmp;
One has to be careful sometimes :)
From what I've read sequence points are also automatically "inserted" at the end of each expression statement.

Hope it helps.
That statement leaves a lot to be desired. "each expression statement" means what when a compiler has taken the instructions from several consecutive source statements and interlaced them like a drunken programmer? The concept "sequence point" is extremely vague when you get down to actual programming and the compiler. Fortunately an accurate data flow graph (which any optimizing compiler produces as a natural work product) takes care of this funny stuff.
Didn't you use to teach this language in college? And you think there is something vague about sequence points? Good lord...

bob
Posts: 20358
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Move time and compiler optimization

Post by bob » Thu Mar 27, 2014 8:13 pm

syzygy wrote:
bob wrote:
mar wrote:Hello Edmund,
as far as I know function calls (whether inline or not) are sequence points (as defined by the standard) so I wouldn't worry there (plus arguments are guaranteed to be evaluated before function body is entered).

A real-life example that happened to me some time ago:

Code: Select all

    	nodes&#91;res&#93;.index = addNode&#40; n->front );
where nodes is a vector that can be changed by subsequent call to recursive method addNode.
What happened is that the compiler cached pointer to nodes before calling addNode which pushes back some elements (sure I might have preallocated nodes in advance by using pre-traversal).
It's because the order of evaluation of assignment operator is not guaranteed (it's not a sequence point unlike && and || operators which are guaranteed to evaluate left to right),
so the compiler is free to evaluate left side first (read where to store the result, not the store itself).

Fixing it was simple enough:

Code: Select all

        int tmp = addNode&#40; n->front );
        nodes&#91;res&#93;.index = tmp;
One has to be careful sometimes :)
From what I've read sequence points are also automatically "inserted" at the end of each expression statement.

Hope it helps.
That statement leaves a lot to be desired. "each expression statement" means what when a compiler has taken the instructions from several consecutive source statements and interlaced them like a drunken programmer? The concept "sequence point" is extremely vague when you get down to actual programming and the compiler. Fortunately an accurate data flow graph (which any optimizing compiler produces as a natural work product) takes care of this funny stuff.
You do not have to show that you have no clue about the C standard.
If you knew 1/2 of what you think you know, you'd stay out of these conversations with your cute one-liners...

bob
Posts: 20358
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Move time and compiler optimization

Post by bob » Thu Mar 27, 2014 8:15 pm

AlvaroBegue wrote:
bob wrote:
mar wrote:Hello Edmund,
as far as I know function calls (whether inline or not) are sequence points (as defined by the standard) so I wouldn't worry there (plus arguments are guaranteed to be evaluated before function body is entered).

A real-life example that happened to me some time ago:

Code: Select all

    	nodes&#91;res&#93;.index = addNode&#40; n->front );
where nodes is a vector that can be changed by subsequent call to recursive method addNode.
What happened is that the compiler cached pointer to nodes before calling addNode which pushes back some elements (sure I might have preallocated nodes in advance by using pre-traversal).
It's because the order of evaluation of assignment operator is not guaranteed (it's not a sequence point unlike && and || operators which are guaranteed to evaluate left to right),
so the compiler is free to evaluate left side first (read where to store the result, not the store itself).

Fixing it was simple enough:

Code: Select all

        int tmp = addNode&#40; n->front );
        nodes&#91;res&#93;.index = tmp;
One has to be careful sometimes :)
From what I've read sequence points are also automatically "inserted" at the end of each expression statement.

Hope it helps.
That statement leaves a lot to be desired. "each expression statement" means what when a compiler has taken the instructions from several consecutive source statements and interlaced them like a drunken programmer? The concept "sequence point" is extremely vague when you get down to actual programming and the compiler. Fortunately an accurate data flow graph (which any optimizing compiler produces as a natural work product) takes care of this funny stuff.
Didn't you use to teach this language in college? And you think there is something vague about sequence points? Good lord...

edit: duplicate post deleted. Apparently my macbook thought I hit submit before I was finished typing.
Last edited by bob on Thu Mar 27, 2014 8:20 pm, edited 2 times in total.

Post Reply