bugmake - Bugs: bug #52076, wildcard/glob should be sorted

 
 

bug #52076: wildcard/glob should be sorted

Submitted by:  Bernhard M. <bmwiedemann>
Submitted on:  Wed 20 Sep 2017 07:43:51 PM UTC  
 
Severity: 3 - NormalItem Group: None
Status: NonePrivacy: Public
Assigned to: NoneOpen/Closed: Open
Component Version: NoneOperating System: None
Fixed Release: NoneTriage Status: None

Add a New Comment(Rich Markup)
   

You are not logged in

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

 

(Jump to the original submission Jump to the original submission)

Wed 18 Oct 2017 07:49:35 PM UTC, comment #17:

Oh, I should correct myself - a naively-implemented quick-sort has that kind of worst-case performance. (Fuzzy memory of undergrad-level compsci.) But hopefully C library authors do not do that.

Ximin Luo <infinity0>
Wed 18 Oct 2017 07:38:19 PM UTC, comment #16:

@eliz quick-sort has O(n^2) performance when sorting an already-sorted list, so it is possible that it affected Windows. But this is again a conjecture, and could be worked around by passing NOSORT only on platforms where readdir() is already sorted.

(I am just throwing things out there in case these conjectures help anyone remember the original reasons for things.)

Ximin Luo <infinity0>
Wed 18 Oct 2017 07:25:11 PM UTC, comment #15:

Hi, just poking this bug report to voice support for sorting $(wildcard) again. It would be more efficient than patching hundreds of upstream projects.

Yes, I understand that "if upstream projects want reproducible builds everywhere they should use $(sort)". That is not incompatible with supporting a sorted $(wildcard) in GNU make. This would improve the default situation at least for GNU/Linux distributions where GNU make is the default. (And it's 2017, this is the majority use-case in the FOSS world at least.)

Later, other Make implementations might follow suit, and we'd welcome this as well - and would actively pursue this, when we find time to do that.

I investigated this issue with Bernhard originally, and also was curious at the lack of documentation pointing to specific discussion around the "performance" issue. Looking at the code, what was actually changed in b9f831b8 was the utility function multi_glob (which today is parse_file_seq), which is also used at various other parts of the code not related to func_wildcard.

What I conjecture is that, if there was a performance issue, it might have been related to those other uses of multi_glob / parse_file_seq and not $(wildcard) itself. (The commit doesn't mention $(wildcard)). Does that ring any bells, Paul? In which case, one possible fix might be to add a SORT parameter to parse_file_seq, make it false by default, but in func_wildcard make it true. Then that would preserve whatever performance improvements that the original code might have made.

Ximin Luo <infinity0>
Thu 12 Oct 2017 08:06:42 AM UTC, comment #14:

individual globs are sorted, i.e. I got
z1 y1 x1 y2

from
<pre>
# cat Makefile
test: prep
echo $(wildcard *1 *2)
prep:
touch z1 y1 y2 x1
</pre>
so the use-cases should be fine.
Not sure why it is reverse order, but that should not matter much.

Bernhard M. <bmwiedemann>
Wed 11 Oct 2017 07:35:30 PM UTC, comment #13:

There are two use-cases I know of where reintroducing sorting might cause problems and need reworking of existing makefiles.

The first is where precedence is wanted. For example:

$(firstword $(wildcard dir1/file dir2/file dir3/file))

Here, file may not exist in all directories and the aim is to find the first instance of file, first looking in dir1, and then dir2, and then dir3 - like a series of -I options on a compiler. With sorting this might need to be changed to:

$(firstword $(wildcard dir1/file) $(wildcard dir2/file) $(wildcard dir3/file))

The second is trying to detect whether all files in a list exist. Currently this can be achieved with:

$(if $(findstring $(files),$(wildcard $(files))),exist,something_missing)

With sorting of wildcard, a sort would also need to be added as follows:

$(if $(findstring $(sort $(files)),$(wildcard $(files))),exist,something_missing)

So this ends up adding two useless sort operations. This second use-case is typically used with sentinel type rules that generate more than one target. Here the aim is to detect if any of the targets are missing and if so then force the sentinel rule to rebuild them.

Neither of these may be a compelling reason to reason to keep things unsorted, and none of them actually use globbing - instead filenames are explicit.

It depends exactly what adding sorting means. Does it mean sorting the result of each individual globbing result in the wildcard separately, or is it sorting the whole result of wildcard.

Given a directory containing:

z1 y1 y2 x1

would $(wildcard *1 *2) return:

x1 y1 z1 y2

or

x1 y1 y2 z1

testing with echo *1 *2 on linux I get the first result, and this result would not break the use-cases.

Anyway, just wanted to point out there are existing makefiles that could be affected if sorting were reintroduced.

Anonymous
Fri 29 Sep 2017 07:42:52 AM UTC, comment #12:

For the record, 'readdir' on MS-Windows returns files in sorted order, because the underlying filesystem APIs do that. So whatever the rationale for this change was, it couldn't be MS-Windows.

Eli Zaretskii <eliz>
Project Member
Sun 24 Sep 2017 07:12:18 PM UTC, comment #11:

Over the last months I pushed dozens of patches to various upstream projects e.g. [1]
so that they use $(sort $(wildcard
but it is a lot of effort and it would never stop,
because people keep creating new code and new Makefiles.

Because (for openSUSE) our goal is to create a distribution that builds reproducibly, we can also include a make with this patch. We will have a different gcc than others anyway, so build results will not be the same on other distributions.

For now, I'm happy when I can fire up two build processes (that happen in disposable VMs) and get the same binary packages out when all the build binaries and sources are the same.

[1] https://github.com/dunst-project/dunst/pull/372/files
https://github.com/01org/libinvm-cli/pull/4/files
https://github.com/01org/libinvm-cim/pull/3/files

Bernhard M. <bmwiedemann>
Sun 24 Sep 2017 02:53:27 PM UTC, comment #10:

The test attached here is not a good one: since you create files in the directory such that they're mostly ordered already, the sort operation doesn't need to do much work.

However, I created my own test using uuidgen to create files named with UUIDs, so that the order of creation in the directory and the sort order would not be correlated at all, and I still didn't see much difference (the ordered version was consistently slower but not in a very significant way).

I don't remember the impetus for this change specifically: there was a request for it. Maybe from one of the alternate ports like Windows or VMS (however both use the glob/* code that comes with make so I'd be surprised if it were terribly impacting). It should be in the mailing list but I can't find it. I suppose it's possible it came to me directly but it seems unlikely; I virtually always at least reply to the list.

I don't particularly mind switching it back again, barring testing on alternative platforms, but David Boyce is correct: it's been unsorted for so long that any portable makefile cannot rely on this sorting behavior for many years to come even if we switch it now. If your goal is to support reproducible builds you'll either need to mandate a particular version of GNU make, or else use $(sort ...) in your makefile explicitly to guarantee order. The latter seems safer to me in any event, if the goal is reproducible builds.

Paul D. Smith <psmith>
Project Administrator
Thu 21 Sep 2017 03:18:19 PM UTC, comment #9:

I thought, the NEWS entry was added shortly after the commit,
but actually there were 13 months in between, thus I now found

https://savannah.gnu.org/bugs/?27381

involving psmith (the commit author) not being sure why it was added, only 3 months after the commit
which I would not expect to be the case if there would have been a lengthy discussion around it.

Also found
https://lists.gnu.org/archive/html/bug-make/2010-07/msg00050.html
with little extra insight

Bernhard M. <bmwiedemann>
Thu 21 Sep 2017 02:38:58 PM UTC, comment #8:

Sorry, missed that.

David Boyce <boyski>
Thu 21 Sep 2017 02:15:45 PM UTC, comment #7:

The commit b9f831b8 is already mentioned in comment 0
But there are no pointers to any related bug or discussion.

Bernhard M. <bmwiedemann>
Thu 21 Sep 2017 02:13:41 PM UTC, comment #6:

Since make has used git for some years now I'd think "git bisect" or "git blame" or similar would be the way to find the commit.

David Boyce <boyski>
Thu 21 Sep 2017 02:07:39 PM UTC, comment #5:

> At the least you should find the original bug report and/or discussion threads and read through them. I'm fairly sure they'd include their own metrics demonstrating the value of GLOB_NOSORT leading to a more informed discussion.


The commit ChangeLog only mentions
https://sourceware.org/bugzilla/show_bug.cgi?id=10246
which is unrelated

and 95f1a32d27eef91a8a037522467d7060e7da2624 which added the NEWS entry links to
http://sv.gnu.org/bugs/index.php?group=make&report_id=111&fix_release_id=104&set=custom
which lists 90 bugs, with a handful related to wildcard
but I found none about performance or sorting

I also glanced over
https://lists.gnu.org/archive/html/bug-make/2009-05/threads.html
https://lists.gnu.org/archive/html/help-make/2009-05/threads.html
and the ones for start of June but also did not find anything
so I would be grateful for a pointer to that previous bug/discussion

OTOH the patch is simple enough that I already considered pushing it into openSUSE which would solve the issue for us, but I thought it would be nicer to let everyone profit from such a nice fix (instead of having to touch 100+ packages to fix each of them individually) to make them build reproducibly.
( See https://reproducible-builds.org/ on why this matters )

Bernhard M. <bmwiedemann>
Thu 21 Sep 2017 02:07:36 PM UTC, comment #4:

There must have been discussion about changing that setting, then removing it, documenting it and reapplying it. Perhaps I even vaguely remember it? You'd think it'd be easy enough to find. I did but I've spent a good ten minutes trying to find it to no avail. It's so easy when a check-in cites a bug number.

Martin Dorey <mdorey>
Thu 21 Sep 2017 01:36:19 PM UTC, comment #3:

I think you're wasting time re-litigating this. It's not a bug, it was a deliberate, documented change from a while ago. The odds of getting it changed back are low, and even if that happened it would be a long time before a release with the change appeared. Not to mention probably decades before you could rely on all versions you care about to have the &quot;new&quot; behavior. Meanwhile, the alternative is to add a $(sort ...) and have a makefile which works reliably. Given the fact that recent released versions don't sort, any portable makefile will need an explicit $(sort ...) even if you succeed in your mission, and then what's the point of succeeding? I understand you might wish this change had never been made and could dispute that decision retroactively but the time to argue against it is long past.

At the least you should find the original bug report and/or discussion threads and read through them. I'm fairly sure they'd include their own metrics demonstrating the value of GLOB_NOSORT leading to a more informed discussion.

David Boyce <boyski>
Thu 21 Sep 2017 03:26:22 AM UTC, comment #2:

I tried to measure the performance difference using the attached 'makebench' files, running in a tmpfs to not have physical disk IO influence results
but found that the difference is so close to zero
that it was lost in noise.

Here is what i got from running it twice each with unsorted and sorted glob:

==unsorted make:

real 0m8,108s
user 0m7,652s
sys 0m0,402s
make: Nothing to be done for 'run'.

real 0m7,706s
user 0m7,496s
sys 0m0,157s

real 0m7,998s
user 0m7,605s
sys 0m0,391s
make: Nothing to be done for 'run'.

real 0m7,634s
user 0m7,489s
sys 0m0,136s

== sorted make:

real 0m8,030s
user 0m7,662s
sys 0m0,372s
make: Nothing to be done for 'run'.

real 0m7,583s
user 0m7,417s
sys 0m0,168s

real 0m8,026s
user 0m7,609s
sys 0m0,423s
make: Nothing to be done for 'run'.

real 0m7,646s
user 0m7,509s
sys 0m0,137s

Do you have a benchmark that better shows the difference?

(file #41853)

Bernhard M. <bmwiedemann>
Wed 20 Sep 2017 08:20:30 PM UTC, comment #1:

This was an intentional change. To quote the NEWS file:

  • WARNING: Backward-incompatibility!

Wildcards were not documented as returning sorted values, but the results
have been sorted up until this release.. If your makefiles require sorted
results from wildcard expansions, use the $(sort ...) function to request
it explicitly.

My recall is that there's a non-trivial performance gain from this for some large projects.

Anonymous
Wed 20 Sep 2017 07:43:51 PM UTC, original submission:

wildcard/glob should be sorted
similar to shell glob, perl glob and POSIX glob(3)

commit b9f831b8 added GLOB_NOSORT for no apparent reason,
possibly by mistake.

man 3 glob is very specific that the only reason to add this flag is
to save processing time, but since ordering actually matters in a
variety of cases, (e.g. when linking .o files into a binary)
the list should be sorted.

Bernhard M. <bmwiedemann>

 

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

Attach File(s):
   
   
Comment:
   

Attached Files
file #41853:  makebench.tar.gz added by bmwiedemann (469B - application/gzip - simple make glob benchmark)
file #41848:  0001-Sort-glob-file-lists.patch added by bmwiedemann (1KiB - text/x-patch - fixing patch)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by infinity0 (Posted a comment)
  • -unavailable- added by eliz (Posted a comment)
  • -unavailable- added by psmith (Posted a comment)
  • -unavailable- added by mdorey (Posted a comment)
  • -unavailable- added by boyski (Posted a comment)
  • -unavailable- added by bmwiedemann (Submitted the item)
  • -unavailable- added by bmwiedemann
  • -unavailable- added by bmwiedemann
  •  

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

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 4 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Thu 21 Sep 2017 03:26:22 AM UTCbmwiedemannAttached File-=>Added makebench.tar.gz, #41853
    Wed 20 Sep 2017 07:43:51 PM UTCbmwiedemannAttached File-=>Added 0001-Sort-glob-file-lists.patch, #41848
      Carbon-Copy-=>Added -unavailable-
      Carbon-Copy-=>Added -unavailable-

    Back to the top


    Powered by Savane 3.1-cleanup1