[PATCH 1/1] scripts: Changed potential O(n) file size calculation to O(1)

[PATCH 1/1] scripts: Changed potential O(n) file size calculation to O(1)

[konrad.schwarz]

The mkemmc.sh script calculates file sizes via `wc -c'.  `wc'
normally works by reading the entire file, resulting in O(n) performance.

Unix file systems obviously know a file's size and POSIX `ls' reports this
information unambiguously, so replacing `wc' with `ls' ensures O(1)
performance.  The files in question tend to be large making this change
worthwhile.

Signed-off-by: Konrad Schwarz <konrad.schwarz@siemens.com>
---
 scripts/mkemmc.sh | 10 ++++++++--
 1 file changed, 8 insertions(+), 2 deletions(-)

diff --git a/scripts/mkemmc.sh b/scripts/mkemmc.sh
index 45dc3f08fa..d2c4e84b16 100755
--- a/scripts/mkemmc.sh
+++ b/scripts/mkemmc.sh
@@ -37,13 +37,19 @@ usage() {
     exit "$1"
 }

+file_size() {
+	ls_line=$(ls -Hdog "$1") || return
+	printf %s\\n "$ls_line" | cut -d\  -f3
+	unset ls_line
+}
+
 process_size() {
     name=$1
     image_file=$2
     alignment=$3
     image_arg=$4
     if [ "${image_arg#*:}" = "$image_arg"  ]; then
-        if ! size=$(wc -c < "$image_file" 2>/dev/null); then
+        if ! size=$(file_size "$image_file"); then
             echo "Missing $name image '$image_file'." >&2
             exit 1
         fi
@@ -105,7 +111,7 @@ check_truncation() {
     if [ "$image_file" = "/dev/zero" ]; then
         return
     fi
-    if ! actual_size=$(wc -c < "$image_file" 2>/dev/null); then
+    if ! actual_size=$(file_size "$image_file"); then
         echo "Missing image '$image_file'." >&2
         exit 1
     fi
-- 
2.39.5

Re: [PATCH 1/1] scripts: Changed potential O(n) file size calculation to O(1)

[Jan Kiszka]

You want to add

From: Konrad Schwarz <konrad.schwarz@siemens.com>

to the top of the commit message when submitting via a different account
so that author and signer are aligned. Or use git sendemail which will
do that when author and submitter address differ.

On 19.11.25 18:28, konrad.schwarz@gmail.com wrote:
> The mkemmc.sh script calculates file sizes via `wc -c'.  `wc'
> normally works by reading the entire file, resulting in O(n) performance.
> 
> Unix file systems obviously know a file's size and POSIX `ls' reports this
> information unambiguously, so replacing `wc' with `ls' ensures O(1)
> performance.  The files in question tend to be large making this change
> worthwhile.

Valid point.

> 
> Signed-off-by: Konrad Schwarz <konrad.schwarz@siemens.com>
> ---
>  scripts/mkemmc.sh | 10 ++++++++--
>  1 file changed, 8 insertions(+), 2 deletions(-)
> 
> diff --git a/scripts/mkemmc.sh b/scripts/mkemmc.sh
> index 45dc3f08fa..d2c4e84b16 100755
> --- a/scripts/mkemmc.sh
> +++ b/scripts/mkemmc.sh
> @@ -37,13 +37,19 @@ usage() {
>      exit "$1"
>  }
> 
> +file_size() {
> +	ls_line=$(ls -Hdog "$1") || return

This will not suppress the error message when a file does not exist or
is not accessible, so:

ls_line=$(ls -Hdog "$1" 2>/dev/null) || return

> +	printf %s\\n "$ls_line" | cut -d\  -f3
> +	unset ls_line
> +}
> +
>  process_size() {
>      name=$1
>      image_file=$2
>      alignment=$3
>      image_arg=$4
>      if [ "${image_arg#*:}" = "$image_arg"  ]; then
> -        if ! size=$(wc -c < "$image_file" 2>/dev/null); then
> +        if ! size=$(file_size "$image_file"); then
>              echo "Missing $name image '$image_file'." >&2
>              exit 1
>          fi
> @@ -105,7 +111,7 @@ check_truncation() {
>      if [ "$image_file" = "/dev/zero" ]; then
>          return
>      fi
> -    if ! actual_size=$(wc -c < "$image_file" 2>/dev/null); then
> +    if ! actual_size=$(file_size "$image_file"); then
>          echo "Missing image '$image_file'." >&2
>          exit 1
>      fi

Thanks,
Jan

-- 
Siemens AG, Foundational Technologies
Linux Expert Center

Re: [PATCH 1/1] scripts: Changed potential O(n) file size calculation to O(1)

[Daniel P. Berrangé]

On Fri, Nov 21, 2025 at 11:16:11AM +0100, Jan Kiszka wrote:
> You want to add
> 
> From: Konrad Schwarz <konrad.schwarz@siemens.com>
> 
> to the top of the commit message when submitting via a different account
> so that author and signer are aligned. Or use git sendemail which will
> do that when author and submitter address differ.
> 
> On 19.11.25 18:28, konrad.schwarz@gmail.com wrote:
> > The mkemmc.sh script calculates file sizes via `wc -c'.  `wc'
> > normally works by reading the entire file, resulting in O(n) performance.
> > 
> > Unix file systems obviously know a file's size and POSIX `ls' reports this
> > information unambiguously, so replacing `wc' with `ls' ensures O(1)
> > performance.  The files in question tend to be large making this change
> > worthwhile.
> 
> Valid point.
> 
> > 
> > Signed-off-by: Konrad Schwarz <konrad.schwarz@siemens.com>
> > ---
> >  scripts/mkemmc.sh | 10 ++++++++--
> >  1 file changed, 8 insertions(+), 2 deletions(-)
> > 
> > diff --git a/scripts/mkemmc.sh b/scripts/mkemmc.sh
> > index 45dc3f08fa..d2c4e84b16 100755
> > --- a/scripts/mkemmc.sh
> > +++ b/scripts/mkemmc.sh
> > @@ -37,13 +37,19 @@ usage() {
> >      exit "$1"
> >  }
> > 
> > +file_size() {
> > +	ls_line=$(ls -Hdog "$1") || return
> 
> This will not suppress the error message when a file does not exist or
> is not accessible, so:
> 
> ls_line=$(ls -Hdog "$1" 2>/dev/null) || return
> 
> > +	printf %s\\n "$ls_line" | cut -d\  -f3
> > +	unset ls_line

This parsing of 'ls' output could be simplified by
using the 'stat' command with a format string to
request only the file size.

    stat --format=%s "$1"


With regards,
Daniel
-- 
|: https://berrange.com      -o-    https://www.flickr.com/photos/dberrange :|
|: https://libvirt.org         -o-            https://fstop138.berrange.com :|
|: https://entangle-photo.org    -o-    https://www.instagram.com/dberrange :|

RE: [PATCH 1/1] scripts: Changed potential O(n) file size calculation to O(1)

[Schwarz, Konrad]

> From: Daniel P. Berrangé <berrange@redhat.com>
> Sent: Friday, November 21, 2025 12:09
> Subject: Re: [PATCH 1/1] scripts: Changed potential O(n) file size calculation to
> O(1)

> > ls_line=$(ls -Hdog "$1" 2>/dev/null) || return
> >
> > > +   printf %s\\n "$ls_line" | cut -d\  -f3
> > > +   unset ls_line
> 
> This parsing of 'ls' output could be simplified by using the 'stat' command
> with a format string to request only the file size.
> 
>     stat --format=%s "$1"

The use of `wc' results from the fact that `stat' is not available on all platforms,
iMacOS in particular, to my knowledge.

RE: [PATCH 1/1] scripts: Changed potential O(n) file size calculation to O(1)

[Schwarz, Konrad]

> From: Kiszka, Jan (FT RPD CED) <jan.kiszka@siemens.com>
> Sent: Friday, November 21, 2025 11:16
> Subject: Re: [PATCH 1/1] scripts: Changed potential O(n) file size calculation to
> O(1)
>  
> >  scripts/mkemmc.sh | 10 ++++++++--
> >  1 file changed, 8 insertions(+), 2 deletions(-)
> >
> > diff --git a/scripts/mkemmc.sh b/scripts/mkemmc.sh index
> > 45dc3f08fa..d2c4e84b16 100755
> > --- a/scripts/mkemmc.sh
> > +++ b/scripts/mkemmc.sh
> > @@ -37,13 +37,19 @@ usage() {
> >      exit "$1"
> >  }
> >
> > +file_size() {
> > +	ls_line=$(ls -Hdog "$1") || return
> 
> This will not suppress the error message when a file does not exist or is not
> accessible, so:
> 
> ls_line=$(ls -Hdog "$1" 2>/dev/null) || return

My take on this is:

`ls' is able to produce informative diagnostic messages as it has
access to `errno'. The additional information, e.g., whether an 'EACCES',
an `ENOENT' or an `ENOTDIR' error has occurred, should in the majority
of cases help the user in fixing the underlying problem. I think it would be
counter-productive to suppress this.

(In fact, one could go further and consider using only the error message
of `ls' and not provide an own error message at all.
In this case, it would be especially easy to return `ls' status back to 
the script's invoker, by simply invoking `exit' without an argument.)

> 
> > +	printf %s\\n "$ls_line" | cut -d\  -f3
> > +	unset ls_line
> > +}
> > +
> >  process_size() {
> >      name=$1
> >      image_file=$2
> >      alignment=$3
> >      image_arg=$4
> >      if [ "${image_arg#*:}" = "$image_arg"  ]; then
> > -        if ! size=$(wc -c < "$image_file" 2>/dev/null); then
> > +        if ! size=$(file_size "$image_file"); then
> >              echo "Missing $name image '$image_file'." >&2
> >              exit 1
> >          fi
> > @@ -105,7 +111,7 @@ check_truncation() {
> >      if [ "$image_file" = "/dev/zero" ]; then
> >          return
> >      fi
> > -    if ! actual_size=$(wc -c < "$image_file" 2>/dev/null); then
> > +    if ! actual_size=$(file_size "$image_file"); then
> >          echo "Missing image '$image_file'." >&2
> >          exit 1
> >      fi
> 
> Thanks,
> Jan
> 
> --
> Siemens AG, Foundational Technologies
> Linux Expert Center

Re: [PATCH 1/1] scripts: Changed potential O(n) file size calculation to O(1)

[Jan Kiszka]

On 21.11.25 14:32, Schwarz, Konrad (FT RPD CED OES-DE) wrote:
>> From: Kiszka, Jan (FT RPD CED) <jan.kiszka@siemens.com>
>> Sent: Friday, November 21, 2025 11:16
>> Subject: Re: [PATCH 1/1] scripts: Changed potential O(n) file size calculation to
>> O(1)
>>  
>>>  scripts/mkemmc.sh | 10 ++++++++--
>>>  1 file changed, 8 insertions(+), 2 deletions(-)
>>>
>>> diff --git a/scripts/mkemmc.sh b/scripts/mkemmc.sh index
>>> 45dc3f08fa..d2c4e84b16 100755
>>> --- a/scripts/mkemmc.sh
>>> +++ b/scripts/mkemmc.sh
>>> @@ -37,13 +37,19 @@ usage() {
>>>      exit "$1"
>>>  }
>>>
>>> +file_size() {
>>> +	ls_line=$(ls -Hdog "$1") || return
>>
>> This will not suppress the error message when a file does not exist or is not
>> accessible, so:
>>
>> ls_line=$(ls -Hdog "$1" 2>/dev/null) || return
> 
> My take on this is:
> 
> `ls' is able to produce informative diagnostic messages as it has
> access to `errno'. The additional information, e.g., whether an 'EACCES',
> an `ENOENT' or an `ENOTDIR' error has occurred, should in the majority
> of cases help the user in fixing the underlying problem. I think it would be
> counter-productive to suppress this.

Even if that was true, you should not fold this change into your O(1)
optimization and argue about that separately.

> 
> (In fact, one could go further and consider using only the error message
> of `ls' and not provide an own error message at all.

I intentionally wanted to handle the error outside of the low-level
function here. The caller should not care how the size is retrieved -
implementation detail.

But the ls approach still has a major issue: It gives a size for a
directory, rather than failing with "not a readable file".

Jan

> In this case, it would be especially easy to return `ls' status back to 
> the script's invoker, by simply invoking `exit' without an argument.)
> 
>>
>>> +	printf %s\\n "$ls_line" | cut -d\  -f3
>>> +	unset ls_line
>>> +}
>>> +
>>>  process_size() {
>>>      name=$1
>>>      image_file=$2
>>>      alignment=$3
>>>      image_arg=$4
>>>      if [ "${image_arg#*:}" = "$image_arg"  ]; then
>>> -        if ! size=$(wc -c < "$image_file" 2>/dev/null); then
>>> +        if ! size=$(file_size "$image_file"); then
>>>              echo "Missing $name image '$image_file'." >&2
>>>              exit 1
>>>          fi
>>> @@ -105,7 +111,7 @@ check_truncation() {
>>>      if [ "$image_file" = "/dev/zero" ]; then
>>>          return
>>>      fi
>>> -    if ! actual_size=$(wc -c < "$image_file" 2>/dev/null); then
>>> +    if ! actual_size=$(file_size "$image_file"); then
>>>          echo "Missing image '$image_file'." >&2
>>>          exit 1
>>>      fi
>>
>> Thanks,
>> Jan
>>
>> --
>> Siemens AG, Foundational Technologies
>> Linux Expert Center

-- 
Siemens AG, Foundational Technologies
Linux Expert Center

Re: [PATCH 1/1] scripts: Changed potential O(n) file size calculation to O(1)

[Paolo Bonzini]

On 11/19/25 18:28, konrad.schwarz@gmail.com wrote:
> The mkemmc.sh script calculates file sizes via `wc -c'.  `wc'
> normally works by reading the entire file, resulting in O(n) performance.

Even something as mundane as 'wc' can surprise you!  Running "strace wc 
-c < somefile.txt" shows this:

fstat(0, {st_mode=S_IFREG|0644, st_size=6900, ...}) = 0
lseek(0, 0, SEEK_CUR)                   = 0
lseek(0, 6900, SEEK_CUR)                = 6900

So wc notices you don't need word or line counts, and takes a shortcut.

Paolo

> Unix file systems obviously know a file's size and POSIX `ls' reports this
> information unambiguously, so replacing `wc' with `ls' ensures O(1)
> performance.  The files in question tend to be large making this change
> worthwhile.
> 
> Signed-off-by: Konrad Schwarz <konrad.schwarz@siemens.com>
> ---
>   scripts/mkemmc.sh | 10 ++++++++--
>   1 file changed, 8 insertions(+), 2 deletions(-)
> 
> diff --git a/scripts/mkemmc.sh b/scripts/mkemmc.sh
> index 45dc3f08fa..d2c4e84b16 100755
> --- a/scripts/mkemmc.sh
> +++ b/scripts/mkemmc.sh
> @@ -37,13 +37,19 @@ usage() {
>       exit "$1"
>   }
> 
> +file_size() {
> +	ls_line=$(ls -Hdog "$1") || return
> +	printf %s\\n "$ls_line" | cut -d\  -f3
> +	unset ls_line
> +}
> +
>   process_size() {
>       name=$1
>       image_file=$2
>       alignment=$3
>       image_arg=$4
>       if [ "${image_arg#*:}" = "$image_arg"  ]; then
> -        if ! size=$(wc -c < "$image_file" 2>/dev/null); then
> +        if ! size=$(file_size "$image_file"); then
>               echo "Missing $name image '$image_file'." >&2
>               exit 1
>           fi
> @@ -105,7 +111,7 @@ check_truncation() {
>       if [ "$image_file" = "/dev/zero" ]; then
>           return
>       fi
> -    if ! actual_size=$(wc -c < "$image_file" 2>/dev/null); then
> +    if ! actual_size=$(file_size "$image_file"); then
>           echo "Missing image '$image_file'." >&2
>           exit 1
>       fi

RE: [PATCH 1/1] scripts: Changed potential O(n) file size calculation to O(1)

[Schwarz, Konrad]

> -----Original Message-----
> From: Paolo Bonzini <pbonzini@redhat.com>
> Sent: Friday, November 21, 2025 15:41
> > The script is designed to be cross-platform
> 
> Sure but it's not broken, just less effective, and the optimization is actually
> quite common. I have just checked and it's in all of GNU coreutils, FreeBSD,
> OpenBSD, NetBSD. Rust uutils does not do it for stdin, though.
> 
> > There is no guarantee that this optimization will be present on all potential
> platforms.
> > OTOH, it is virtually guaranteed that `ls' will always `stat()' the
> > file.  It would seem prudent to avoid potential pitfalls.
> 
> Parsing the output of "ls" is also a potential pitfall. In particular, I am not sure
> what happens if $image_file has a newline.  Maybe this is better:
> 
>     ls -Hdog "$1" | {
>         read ls_ign1 ls_ign2 ls_size ls_rest
>         echo $ls_size
>     }

You are right, I forgot about this case.

A perhaps simpler solution is to use `ls -Hdogq', which replaces non-printing characters
(including newline) in the filename with a `?'.