linux-kernel - Re: [PATCH v3] tags: much faster, parallel "make tags"

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <554D9606.7090908@draigBrady.com>
Date:	Sat, 09 May 2015 06:07:18 +0100
From:	Pádraig Brady <P@...igBrady.com>
To:	Alexey Dobriyan <adobriyan@...il.com>, akpm@...ux.foundation.org,
	mmarek@...e.cz
CC:	linux-kernel@...r.kernel.org
Subject: Re: [PATCH v3] tags: much faster, parallel "make tags"

On 08/05/15 14:26, Alexey Dobriyan wrote:
> ctags is single-threaded program. Split list of files to be tagged into
> equal parts, 1 part for each CPU and then merge the results.
> 
> Speedup on one 2-way box I have is ~143 s => ~99 s (-31%).
> On another 4-way box: ~120 s => ~65 s (-46%!).
> 
> Resulting "tags" files aren't byte-for-byte identical because ctags
> program numbers anon struct and enum declarations with "__anonNNN"
> symbols. If those lines are removed, "tags" file becomes byte-for-byte
> identical with those generated with current code.
> 
> Signed-off-by: Alexey Dobriyan <adobriyan@...il.com>
> ---
> 
>  scripts/tags.sh |   36 +++++++++++++++++++++++++++++++-----
>  1 file changed, 31 insertions(+), 5 deletions(-)
> 
> --- a/scripts/tags.sh
> +++ b/scripts/tags.sh
> @@ -152,7 +152,19 @@ dogtags()
>  
>  exuberant()
>  {
> -	all_target_sources | xargs $1 -a                        \
> +	rm -f .make-tags.*
> +
> +	all_target_sources >.make-tags.src
> +	NR_CPUS=$(getconf _NPROCESSORS_ONLN 2>/dev/null || echo 1)

`nproc` is simpler and available since coreutils 8.1 (2009-11-18)

> +	NR_LINES=$(wc -l <.make-tags.src)
> +	NR_LINES=$((($NR_LINES + $NR_CPUS - 1) / $NR_CPUS))
> +
> +	split -a 6 -d -l $NR_LINES .make-tags.src .make-tags.src.

`split -d -nl/$(nproc)` is simpler and available since coreutils 8.8 (2010-12-22)

> +
> +	for i in .make-tags.src.*; do
> +		N=$(echo $i | sed -e 's/.*\.//')
> +		# -u: don't sort now, sort later
> +		xargs <$i $1 -a -f .make-tags.$N -u		\
>  	-I __initdata,__exitdata,__initconst,			\
>  	-I __cpuinitdata,__initdata_memblock			\
>  	-I __refdata,__attribute,__maybe_unused,__always_unused \
> @@ -211,7 +223,21 @@ exuberant()
>  	--regex-c='/DEFINE_PCI_DEVICE_TABLE\((\w*)/\1/v/'		\
>  	--regex-c='/(^\s)OFFSET\((\w*)/\2/v/'				\
>  	--regex-c='/(^\s)DEFINE\((\w*)/\2/v/'				\
> -	--regex-c='/DEFINE_HASHTABLE\((\w*)/\1/v/'
> +	--regex-c='/DEFINE_HASHTABLE\((\w*)/\1/v/'			\
> +	&
> +	done
> +	wait
> +	rm -f .make-tags.src .make-tags.src.*
> +
> +	# write header
> +	$1 -f $2 /dev/null
> +	# remove headers
> +	for i in .make-tags.*; do
> +		sed -i -e '/^!/d' $i &
> +	done
> +	wait
> +	sort .make-tags.* >>$2
> +	rm -f .make-tags.*

Using sort --merge would speed up significantly?

Even faster would be to get sort to skip the header lines, avoiding the need for sed.
It's a bit awkward and was discussed at:
http://lists.gnu.org/archive/html/coreutils/2013-01/msg00027.html
Summarising that, is if not using merge you can:

  tlines=$(($(wc -l < "$2") + 1))
  tail -q -n+$tlines .make-tags.* | LC_ALL=C sort >>$2

Or if merge is appropriate then:

  tlines=$(($(wc -l < "$2") + 1))
  eval "eval LC_ALL=C sort -m '<(tail -n+$tlines .make-tags.'{1..$(nproc)}')'" >>$2

Note eval is fine here as inputs are controlled within the script

cheers,
Pádraig.

p.s. To avoid temp files altogether you could wire everything up through fifos,
though that's probably overkill here TBH

p.p.s. You may want to `trap EXIT cleanup` to rm -f .make-tags.*
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/