Re: include has quadratic complexity

[Philip Guenther]

On Sun, May 19, 2013 at 12:13 PM, Jed Brown <address@hidden> wrote:
> When using the compiler to generate dependencies via -MMD or similar, we
> end up with a large number of *.d files to include.  Unfortunately, the
> include directive scales quadratically in the number of files to include
> (whether or not the files exist).
>
> $ cat > Makefile <<EOF
> all:
>
> -include $(shell seq 1 $N)
> EOF
>
> make-3.82:
>
> $ time make -q N=2000
> 0.623 real   0.610 user   0.010 sys   99.50 cpu
> $ time make -q N=4000
> 2.336 real   2.313 user   0.020 sys   99.87 cpu
> $ time make -q N=8000
> 9.407 real   9.300 user   0.083 sys   99.74 cpu
> $ time make -q N=16000
> 43.844 real   43.753 user   0.090 sys   99.99 cpu
...
> Is it feasible to make 'include' have quasi-linear complexity in the
> number of files?

Try telling make that the include files are always up to date:

$ cat Makefile
all:

M = $(shell jot $N 1)
${M}: ;
-include ${M}
$ time make -q N=1
    0m0.00s real     0m0.00s user     0m0.00s system
$ time make -q N=10
    0m0.00s real     0m0.00s user     0m0.00s system
$ time make -q N=100
    0m0.01s real     0m0.00s user     0m0.01s system
$ time make -q N=1000
    0m0.03s real     0m0.01s user     0m0.00s system
$ time make -q N=10000
    0m0.29s real     0m0.06s user     0m0.22s system
$ time make -q N=100000
    0m3.65s real     0m1.51s user     0m2.20s system
$


After commenting out the "${M}: ;"

$ time make -q N=1
    0m0.00s real     0m0.00s user     0m0.00s system
$ time make -q N=10
    0m0.01s real     0m0.00s user     0m0.00s system
$ time make -q N=100
    0m0.05s real     0m0.00s user     0m0.00s system
$ time make -q N=1000
    0m0.65s real     0m0.39s user     0m0.25s system
$ time make -q N=10000
    1m49.17s real     1m42.75s user     0m2.91s system
$


Philip Guenther