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

 
 

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

Submitted by:  Cassio Neri <cassioneri>
Submitted on:  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:  Bernhard Voelker <berny>
Originator Name:  Cassio Neri Open/Closed:  Open
Release:  4.7.0 Fixed Release:  None

Add a New Comment (Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

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>
Project 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>
Project AdministratorIn charge of this item.
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)
  •  

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

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