bugfindutils - Bugs: bug #58427, Cost-base optimiser breaks...

 
 

bug #58427: Cost-base optimiser breaks short-circuit evaluation

Submitter:  Cassio Neri <cassioneri>
Submitted:  Fri 22 May 2020 09:54:36 AM UTC
   
 
Category:  find Severity:  3 - Normal
Item Group:  Wrong result Status:  In Progress
Privacy:  Public Assigned to:  berny
Originator Name:  Cassio Neri Open/Closed:  Open
Release:  4.7.0 Fixed Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Tue 26 May 2020 11:42:48 AM UTC, comment #3: 

I agree with disabling arm-awapping for -O0.

I agree that we should fix the inconsistency between documentation and implementation regarding the default optimization level.

I agree that arm-swapping E1 -a E2, or arm-awapping E1 -o E2 for any case where the order of evaluation is user-visible is a bug.   Specifically, the only way the user should be able to determine that the execution order has been modified is by using the -D option to ask find what the executed version of the expression is.

As a corollary, it should not be necessary for the user to specify POSIXLY_CORRECT in order to inhibit arm-awapping and thus get correct behaviour.   The user should also, for what it's worth, get correct behaviour for -On for any integer value of n.

Since we currently have a bug, I am OK with any of the obvious approaches to fixing this in the short term (e.g. defaulting to a lower -O value, entirely disabling arm-awapping for now, etc.)

Properly detecting interactions between EXPR1 and EXPR2 seems to be the desirable way to go in the longer term, but for now if we can't do that we may need to disable some features in order to restore correct behaviour.   Perhaps that could be a short-term solution.

While I don't object to adding a configure option to set the default optimisation level, I also don't think it's fair to "export" responsibility for mitigating this problem to packagers.

On the Cost-Based Optimizer more generally, I don't think there have been any systematic measurements of its effectiveness.   It is not impossible that performance benefits arising from it may turn out to be either too small to measure or too small to justify the ongoing maintenance burden that the code imposes.   I wrote the code but I'm not sentimental about it.  If the benefit obtained by keeping it is less then the cost of doing so, we should probably remove it.

Lastly on the spelling aspect, the origin of the problem arises in differences between UK English (of which I am a speaker) and US English.  US English standardised on -ize endings for a lot of words where correct UK English is -ise.   However, the word "atomize" is not one of those words.  In UK English "atomize" is correct.   But because many people are aware of the -ize/-ise differences, there is a popular assumption among UK English speakers that the -ise form should be used there there is an -ize ending in US English.   That's not always the case, but it has led to "atomise" becoming an accepted UK English alternative form of the correct UK English word "atomize".    The same is true of the word "optimize".  I'm to blame for the introduction of "optimise" into the findutils documentation.  Sorry.  All uses of "optimise" should be changed to "optimize".

James Youngman <jay>
Group administrator
Tue 26 May 2020 07:03:56 AM UTC, comment #2: 

Thanks for the report.

I see the following problems:

  • Using -O0 does not turn off arm-swapping completely for those who want that.  I suggest to change that so that -O0 skips arm-swapping.


  • POSIX states for "expression [-a] expression" that "the second expression shall not be evaluated if the first expression is false".  The optimizer violates this rule. Still, I think that CBO makes sense where no side effects are known.   I suggest to:
    • default to level 0 when POSIXLY_CORRECT is set (overridable by the -O option),
    • fix cases like this reported one where later tests can have side effects like EPERM.


  • The documentation about the default -O level states wrongly that the default level would be 1 while it is hard-coded to 2 in util.c:set_option_defaults().


  • The packager cannot choose the default optimization level.  I suggest a new configure option to make this possible.


Finally:

  • findutils uses "optimize" vs. "optimise" quite inconsistently in its code and documentation, with the latter (British English) having more hits than the former (American English).  I suggest to harmonize in the one or the other direction.


@James: WDYT?

Bernhard Voelker <berny>
Group administrator
Fri 22 May 2020 02:13:49 PM UTC, comment #1: 

I noticed something similar before too with -xtype, which was agreed to be a bug: https://savannah.gnu.org/bugs/?51926#comment5

Tavian Barnes <tavianator>
Fri 22 May 2020 09:54:36 AM UTC, original submission:  

Man and info pages say (in different places with different words)

'EXPR1 EXPR2'
'EXPR1 -a EXPR2'
'EXPR1 -and EXPR2'
     And; EXPR2 is not evaluated if EXPR1 is false.

Some might rely on this short-circuit evaluation to prevent errors. However, the cost-based optimiser changes the evaluation order and EXPR2 might be evaluated even when EXPR1 is false. Here is an example:

mkdir some_dir
chmod 333 some_dir
find * -readable ! -empty -printf "yes" -or -printf "no" -prune

which yields

find: ‘some_dir’: Permission denied
no

The "Permission denied" in the output suggests that -readable is false but find evaluates -empty anyway. (Removing ! -empty from the expression makes the error go away.) The optimised tree (edited for the sake of brevity and clarity) is:

(  (  ( ! -empty ) -and -readable ) -and -printf "yes" ) -or ( -printf "no" -and -prune )

In this form, -empty is always evaluated (before -readable).

I hope this not a big diversion from the point but my ruminations on the problem follow. Find's code assumes that AND and OR are commutative which is true under pure boolean logic rules. However, with the addition of short-circuiting these operators loose that property. (Some expressions do commute but not all.) The code must understand that when EXPR1 affects (for some definition of "affects") EXPR2, then they don't commute.

I first posted this question here:
https://stackoverflow.com/q/61937006/1137388

Cassio Neri <cassioneri>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by jay (Posted a comment)
  • -email is unavailable- added by berny (Posted a comment)
  • -email is unavailable- added by tavianator (Posted a comment)
  • -email is unavailable- added by cassioneri (Submitted the item)
  • -email is unavailable- added by cassioneri (bug report on findutils)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only logged-in users can vote.

     

    Follow 3 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2020-05-26 berny StatusNone In Progress
        Assigned toNone berny
    2020-05-22 cassioneri Carbon-Copy- Added cassioneri

    Back to the top

    Powered by Savane 3.13-4448.
    Corresponding source code