signrom: Speed up checksum calculation

RFC PATCH In review Jan Kiszka 7 participants 12 messages Jan 23, 2012 – Jan 24, 2012

Share & tools

Jan Kiszka

author

2012-01-23 18:38 UTC #0 lore raw

RFC PATCH 1/1 signrom: Speed up checksum calculation

Forking an expr process for every byte of the input data slows down the checksum calculation massively. Fix this while still remaining portable by implementing the algorithm in awk.

Signed-off-by Jan Kiszka <[email protected]>

---

That "remaining portable" is an unproven claim. So please check that problematic NetBSD and also mingw. Thanks!

 scripts/signrom.sh |   18 ++++++++----------
 1 files changed, 8 insertions(+), 10 deletions(-)

scripts/signrom.sh +8 ~~-10~~

index 9dc5c63..f0f460e 100755
@@ -23,22 +23,20 @@
 # did we get proper arguments?
 test "$1" -a "$2" || exit 1
 
-sum=0
-
 # find out the file size
 x=`dd if="$1" bs=1 count=1 skip=2 2>/dev/null | od -t u1 -A n`
-#size=`expr $x \* 512 - 1`
 size=$(( $x * 512 - 1 ))
 
 # now get the checksum
 nums=`od -A n -t u1 -v -N $size "$1"`
-for i in ${nums}; do
-    # add each byte's value to sum
-    sum=`expr \( $sum + $i \) % 256`
-done
-
-sum=$(( (256 - $sum) % 256 ))
-sum_octal=$( printf "%o" $sum )
+sum_octal=`echo $nums | awk 'BEGIN {
+    getline data_str;
+    sum = 0;
+    n = split(data_str, data, " ");
+    for (i = 1; i <= n; i++)
+        sum = ( sum + data[i] ) % 256;
+    printf "%o", (256 - sum) % 256;
+}'`
 
 # and write the output file
 cp "$1" "$2"

Signature · 1 line

1.7.3.4

Stefan Weil

2012-01-23 19:16 UTC #1 lore raw

Am 23.01.2012 19:38, schrieb Jan Kiszka:

Quoted 39 lines

Forking an expr process for every byte of the input data slows down the checksum calculation massively. Fix this while still remaining portable by implementing the algorithm in awk.
Signed-off-by Jan Kiszka<[email protected]>
---
That "remaining portable" is an unproven claim. So please check that problematic NetBSD and also mingw. Thanks!
  scripts/signrom.sh |   18 ++++++++----------
  1 files changed, 8 insertions(+), 10 deletions(-)
scripts/signrom.sh +1 ~~-10~~
index 9dc5c63..f0f460e 100755
@@ -23,22 +23,20 @@
  # did we get proper arguments?
  test "$1" -a "$2" || exit 1
 
-sum=0
-
  # find out the file size
  x=`dd if="$1" bs=1 count=1 skip=2 2>/dev/null | od -t u1 -A n`
-#size=`expr $x \* 512 - 1`
  size=$(( $x * 512 - 1 ))
 
  # now get the checksum
  nums=`od -A n -t u1 -v -N $size "$1"`
-for i in ${nums}; do
-    # add each byte's value to sum
-    sum=`expr $ $sum + $i $ % 256`
-done
-
-sum=$(( (256 - $sum) % 256 ))
-sum_octal=$( printf "%o" $sum )
+sum_octal=`echo $nums | awk 'BEGIN {

scripts/signrom.sh line 42

Quoted 10 lines

scripts/signrom.sh +7 -0

+    getline data_str;
+    sum = 0;
+    n = split(data_str, data, " ");
+    for (i = 1; i<= n; i++)
+        sum = ( sum + data[i] ) % 256;
+    printf "%o", (256 - sum) % 256;
+}'`
 
  # and write the output file
  cp "$1" "$2"

What about replacing the whole script by a python script? That would save about 6 more forks :-)

I'd prefer if we could get rid of all AWK dependencies in QEMU and focus on as few scripting languages as reasonable.

Regards,
Stefan W.

Jan Kiszka

author

2012-01-23 19:19 UTC #2 lore raw

Quoted 47 lines · Stefan Weil

Am 23.01.2012 19:38, schrieb Jan Kiszka:
Quoted 46 lines
Forking an expr process for every byte of the input data slows down the checksum calculation massively. Fix this while still remaining portable by implementing the algorithm in awk.
Signed-off-by Jan Kiszka<[email protected]>
---
That "remaining portable" is an unproven claim. So please check that problematic NetBSD and also mingw. Thanks!
  scripts/signrom.sh |   18 ++++++++----------
  1 files changed, 8 insertions(+), 10 deletions(-)
scripts/signrom.sh +8 ~~-10~~
index 9dc5c63..f0f460e 100755
@@ -23,22 +23,20 @@
  # did we get proper arguments?
  test "$1" -a "$2" || exit 1
 
-sum=0
-
  # find out the file size
  x=`dd if="$1" bs=1 count=1 skip=2 2>/dev/null | od -t u1 -A n`
-#size=`expr $x \* 512 - 1`
  size=$(( $x * 512 - 1 ))
 
  # now get the checksum
  nums=`od -A n -t u1 -v -N $size "$1"`
-for i in ${nums}; do
-    # add each byte's value to sum
-    sum=`expr $ $sum + $i $ % 256`
-done
-
-sum=$(( (256 - $sum) % 256 ))
-sum_octal=$( printf "%o" $sum )
+sum_octal=`echo $nums | awk 'BEGIN {
+    getline data_str;
+    sum = 0;
+    n = split(data_str, data, " ");
+    for (i = 1; i<= n; i++)
+        sum = ( sum + data[i] ) % 256;
+    printf "%o", (256 - sum) % 256;
+}'`
 

Quoted 6 lines

scripts/signrom.sh line 42
Quoted 3 lines
scripts/signrom.sh +0 -0
  # and write the output file
  cp "$1" "$2"
What about replacing the whole script by a python script? That would save about 6 more forks :-)

I think we have no python dependency in the build system yet - while we have for awk. That was also the original reason to go for a shell script.

If the situation changed, I would not vote against python, for sure.

Jan

Signature · 2 lines

Siemens AG, Corporate Technology, CT T DE IT 1
Corporate Competence Center Embedded Linux

Stefan Weil

2012-01-23 19:25 UTC #3 lore raw

Am 23.01.2012 20:19, schrieb Jan Kiszka:

Quoted 3 lines · Stefan Weil

Quoted 2 lines
Am 23.01.2012 19:38, schrieb Jan Kiszka:

[snip]

Quoted 9 lines

Quoted 2 lines
What about replacing the whole script by a python script? That would save about 6 more forks :-)
I think we have no python dependency in the build system yet - while we have for awk. That was also the original reason to go for a shell script.
If the situation changed, I would not vote against python, for sure.
Jan

We do. Even configure will fail now without Python:

if ! has $python; then
echo "Python not found. Use --python=/path/to/python" exit 1
fi

QEMU depends on Python = Python 2 for QAPI, tracing and maybe more. See scripts/*.py.

Stefan

Anthony Liguori

2012-01-23 20:08 UTC #4 lore raw

Quoted 17 lines · Stefan Weil

Am 23.01.2012 20:19, schrieb Jan Kiszka:
Quoted 3 lines · Stefan Weil
Quoted 2 lines
Am 23.01.2012 19:38, schrieb Jan Kiszka:
[snip]
Quoted 9 lines
Quoted 2 lines
What about replacing the whole script by a python script? That would save about 6 more forks :-)
I think we have no python dependency in the build system yet - while we have for awk. That was also the original reason to go for a shell script.
If the situation changed, I would not vote against python, for sure.
Jan
We do. Even configure will fail now without Python:

Quoted 7 lines

if ! has $python; then
echo "Python not found. Use --python=/path/to/python" exit 1
fi
QEMU depends on Python = Python 2 for QAPI, tracing and maybe more. See scripts/*.py.

I've been thinking that we could potentially rewrite a large chunk (all?) of configure in python too since we have such a hard dependency now.

Regards,

Anthony Liguori

Quoted 4 lines

Stefan

Jan Kiszka

2012-01-23 20:32 UTC #5 lore raw

Quoted 24 lines · Anthony Liguori

Quoted 23 lines · Stefan Weil
Am 23.01.2012 20:19, schrieb Jan Kiszka:
Quoted 3 lines · Stefan Weil
Quoted 2 lines
Am 23.01.2012 19:38, schrieb Jan Kiszka:
[snip]
Quoted 10 lines
Quoted 2 lines
What about replacing the whole script by a python script? That would save about 6 more forks :-)
I think we have no python dependency in the build system yet - while we have for awk. That was also the original reason to go for a shell script.
If the situation changed, I would not vote against python, for sure.
Jan
We do. Even configure will fail now without Python:
if ! has $python; then
echo "Python not found. Use --python=/path/to/python" exit 1
fi

Quoted 5 lines

Quoted 2 lines
QEMU depends on Python = Python 2 for QAPI, tracing and maybe more. See scripts/*.py.
I've been thinking that we could potentially rewrite a large chunk (all?) of configure in python too since we have such a hard dependency now.

Sounds almost like a GSoC project. Or work for someone who did something nasty ;). At least it's no afternoon hack when done properly.

However, I will now write signrom.py. That's much shorter.

Jan

Anthony Liguori

2012-01-23 20:37 UTC #6 lore raw

Quoted 25 lines · Jan Kiszka

Quoted 24 lines · Anthony Liguori
Quoted 23 lines · Stefan Weil
Am 23.01.2012 20:19, schrieb Jan Kiszka:
Quoted 3 lines · Stefan Weil
Quoted 2 lines
Am 23.01.2012 19:38, schrieb Jan Kiszka:
[snip]
Quoted 10 lines
Quoted 2 lines
What about replacing the whole script by a python script? That would save about 6 more forks :-)
I think we have no python dependency in the build system yet - while we have for awk. That was also the original reason to go for a shell script.
If the situation changed, I would not vote against python, for sure.
Jan
We do. Even configure will fail now without Python:
if ! has $python; then
echo "Python not found. Use --python=/path/to/python" exit 1
fi

Quoted 7 lines

Quoted 5 lines
Quoted 2 lines
QEMU depends on Python = Python 2 for QAPI, tracing and maybe more. See scripts/*.py.
I've been thinking that we could potentially rewrite a large chunk (all?) of configure in python too since we have such a hard dependency now.
Sounds almost like a GSoC project.

That's a good idea!

Quoted 1 line

Or work for someone who did something nasty ;).

Shhh, don't tell any students that :-)

Regards,

Anthony Liguori

Quoted 6 lines

At least it's no afternoon hack when done properly.
However, I will now write signrom.py. That's much shorter.
Jan

Stefan Weil

2012-01-23 21:32 UTC #7 lore raw

Quoted 4 lines · Jan Kiszka

Quoted 3 lines · Anthony Liguori
I've been thinking that we could potentially rewrite a large chunk (all?) of configure in python too since we have such a hard dependency now.

[snip]

Quoted 3 lines

However, I will now write signrom.py. That's much shorter.
Jan

I think that will improve that script (and maybe configure later) a lot. Let me just add a small remark:

We require python2 now, but please try to be compatible with python3 as far as possible. It _is_ possible, at least to some degree (I tried it with the existing QEMU scripts).

I don't believe that QEMU will stick to python2 forever, so avoiding unnecessary incompatibilities now will save us time later.

Cheers,
Stefan

Andreas Färber

2012-01-24 09:45 UTC #8 lore raw

In reply to Anthony Liguori

Am 23.01.2012 21:37, schrieb Anthony Liguori:

Quoted 9 lines · Jan Kiszka

Quoted 6 lines · Anthony Liguori
Quoted 3 lines
I've been thinking that we could potentially rewrite a large chunk (all?) of configure in python too since we have such a hard dependency now.
Sounds almost like a GSoC project.
That's a good idea!

Having a signrom.py, driven by configure or make, is fine.

But configure should be able to run anywhere and at least report what's missing. #!/bin/sh is the standard, highly compatible mechanism among Unices, Posices and more to do just that. Python on the other hand is either /usr/bin/python or /usr/bin/env python, which both don't work on systems without /usr/bin for starters.

So please not all of configure, at least detect and/or allow to overwrite the python path.

Andreas

Signature · 2 lines

SUSE LINUX Products GmbH, Maxfeldstr. 5, 90409 Nürnberg, Germany
GF: Jeff Hawn, Jennifer Guild, Felix Imendörffer; HRB 16746 AG Nürnberg

Paolo Bonzini

2012-01-24 08:18 UTC #9 lore raw

In reply to Anthony Liguori

Quoted 6 lines · Anthony Liguori

Quoted 3 lines
QEMU depends on Python = Python 2 for QAPI, tracing and maybe more. See scripts/*.py.
I've been thinking that we could potentially rewrite a large chunk (all?) of configure in python too since we have such a hard dependency now.

What would the advantages be??

Paolo

Christoph Egger

2012-01-24 11:04 UTC #10 lore raw

In reply to Stefan Weil

Quoted 10 lines · Stefan Weil

Am 23.01.2012 19:38, schrieb Jan Kiszka:
Quoted 9 lines
Forking an expr process for every byte of the input data slows down the checksum calculation massively. Fix this while still remaining portable by implementing the algorithm in awk.
Signed-off-by Jan Kiszka<[email protected]>
---
That "remaining portable" is an unproven claim. So please check that problematic NetBSD and also mingw. Thanks!

The "unproven claim" is actually what SuSv3 spec
(http://pubs.opengroup.org/onlinepubs/009695399/utilities/od.html)
says:

"and the output from each of the transformations shall be separated by one or more <blank>s."

The actual problem is that the programmer expects the behaviour of either GNU od(1) or AT&T UNIX od(1) rather the SuSv3 spec.

NetBSD has AT&T UNIX od(1).

Christoph

Quoted 50 lines

Quoted 37 lines
scripts/signrom.sh | 18 ++++++++----------
1 files changed, 8 insertions(+), 10 deletions(-)
scripts/signrom.sh +0 -0
index 9dc5c63..f0f460e 100755
@@ -23,22 +23,20 @@
 # did we get proper arguments?
test "$1" -a "$2" || exit 1
scripts/signrom.sh +0 -2
-sum=0
-
# find out the file size
x=`dd if="$1" bs=1 count=1 skip=2 2>/dev/null | od -t u1 -A n`
-#size=`expr $x \* 512 - 1`
size=$(( $x * 512 - 1 ))
# now get the checksum
nums=`od -A n -t u1 -v -N $size "$1"`
scripts/signrom.sh +8 -7
-for i in ${nums}; do
- # add each byte's value to sum
- sum=`expr $ $sum + $i $ % 256`
-done
-
-sum=$(( (256 - $sum) % 256 ))
-sum_octal=$( printf "%o" $sum )
+sum_octal=`echo $nums | awk 'BEGIN {
+ getline data_str;
+ sum = 0;
+ n = split(data_str, data, " ");
+ for (i = 1; i<= n; i++)
+ sum = ( sum + data[i] ) % 256;
+ printf "%o", (256 - sum) % 256;
+}'`
Quoted 2 lines
# and write the output file
cp "$1" "$2"
What about replacing the whole script by a python script? That would save about 6 more forks :-)
I'd prefer if we could get rid of all AWK dependencies in QEMU and focus on as few scripting languages as reasonable.
Regards,
Stefan W.

Signature · 6 lines

---to satisfy European Law for business letters:
Advanced Micro Devices GmbH
Einsteinring 24, 85689 Dornach b. Muenchen
Geschaeftsfuehrer: Alberto Bozzo, Andrew Bowd
Sitz: Dornach, Gemeinde Aschheim, Landkreis Muenchen
Registergericht Muenchen, HRB Nr. 43632

Paolo Bonzini

2012-01-24 08:40 UTC #11 lore raw

In reply to Jan Kiszka

scripts/signrom.sh line 40

Quoted 7 lines · Jan Kiszka

nums=od -A n -t u1 -v -N $size "$1"

scripts/signrom.sh +0 -6

-for i in ${nums}; do
-    # add each byte's value to sum
-    sum=`expr \( $sum + $i \) % 256`
-done
-
-sum=$(( (256 - $sum) % 256 ))

We have a bashism here, so why not do

  sum=$(( ($sum + $i) % 256 ))

and do the same with a one-line patch (two line if you change the header to #!/bin/bash)? It should be just as fast as awk.

Paolo