use shuf to choose a random file
v3 cover use shuf to choose a random file
Currently, we use "ls ... | sort -R | head -n1" (or tail) to choose a random file in a directory.It sorts the files with "ls", sort it randomly and pick the first line, which wastes the "ls" sort.
Also, using "sort -R | head -n1" is inefficient. Furthermore, even without "head" or "tail", "shuf" is faster than "sort -R".
This series introduces a new helper _random_file() to choose a file in a directory randomly. Also, replace "sort -R" with _random_file() or "shuf".
Changes:
- v2
- Introduce _random_file() helper
- Rewrite other "sort -R" with _random_file() or "shuf"
- v3
- Fix _random_file() helper to add the base directory as prefix
Naohiro Aota (3):
common/rc: introduce _random_file() helper
fstests/btrfs: use _random_file() helper
btrfs/004: use shuf to shuffle the file lines
common/rc | 7 +++++++ tests/btrfs/004 | 2 +- tests/btrfs/179 | 9 ++++----- tests/btrfs/192 | 14 ++++---------- 4 files changed, 16 insertions(+), 16 deletions(-)
Signature · 1 line
2.41.0
PATCH v3 1/3 common/rc: introduce _random_file() helper
Currently, we use "ls ... | sort -R | head -n1" (or tail) to choose a random file in a directory.It sorts the files with "ls", sort it randomly and pick the first line, which wastes the "ls" sort.
Also, using "sort -R | head -n1" is inefficient. For example, in a directory with 1000000 files, it takes more than 15 seconds to pick a file.
$ time bash -c "ls -U | sort -R | head -n 1 >/dev/null" bash -c "ls -U | sort -R | head -n 1 >/dev/null" 15.38s user 0.14s system 99% cpu 15.536 total
$ time bash -c "ls -U | shuf -n 1 >/dev/null" bash -c "ls -U | shuf -n 1 >/dev/null" 0.30s user 0.12s system 138% cpu 0.306 total
So, we should just use "ls -U" and "shuf -n 1" to choose a random file. Introduce _random_file() helper to do it properly.
--- common/rc | 7 +++++++ 1 file changed, 7 insertions(+)
common/rc +7 -0
@@ -5224,6 +5224,13 @@ _soak_loop_running() { return 0 } +# Return a random file in a directory. A directory is *not* followed +# recursively. +_random_file() { + local basedir=$1 + echo "$basedir/$(ls -U $basedir | shuf -n 1)" +} + init_rc ################################################################################
Signature · 1 line
2.41.0
Re: [PATCH v3 1/3] common/rc: introduce _random_file() helper
LGTM
Re: [PATCH v3 1/3] common/rc: introduce _random_file() helper
In reply to Naohiro AotaQuoted 26 lines · Naohiro Aota
Currently, we use "ls ... | sort -R | head -n1" (or tail) to choose a random file in a directory.It sorts the files with "ls", sort it randomly and pick the first line, which wastes the "ls" sort.
Also, using "sort -R | head -n1" is inefficient. For example, in a directory with 1000000 files, it takes more than 15 seconds to pick a file.
$ time bash -c "ls -U | sort -R | head -n 1 >/dev/null" bash -c "ls -U | sort -R | head -n 1 >/dev/null" 15.38s user 0.14s system 99% cpu 15.536 total$ time bash -c "ls -U | shuf -n 1 >/dev/null" bash -c "ls -U | shuf -n 1 >/dev/null" 0.30s user 0.12s system 138% cpu 0.306 totalSo, we should just use "ls -U" and "shuf -n 1" to choose a random file. Introduce
_random_file()helper to do it properly.Signed-off-by Naohiro Aota <[email protected]>--- common/rc | 7 +++++++ 1 file changed, 7 insertions(+)common/rc +0
-0
common/rc _soak_loop_running() { · line 5231
Quoted 8 lines
common/rc +5
-0@@ -5224,6 +5224,13 @@ _soak_loop_running() { return 0 } +# Return a random file in a directory. A directory is *not* followed +# recursively. +_random_file() { + local basedir=$1 + echo "$basedir/$(ls -U $basedir | shuf -n 1)"
I think the "1" can be the second argument, for we might want to get a random file list sometimes. For example:
local basedir=$1
local num=$2
local opt
if [ -n "$num" ];then
opt="-n $num"
fi
echo "$basedir/$(ls -U $basedir | shuf $opt)"
What do you think?
Thanks,
Zorro
Quoted 8 lines
common/rc +2
-0+} + init_rc ################################################################################Signature · 1 line
2.41.0
Re: [PATCH v3 1/3] common/rc: introduce _random_file() helper
Quoted 43 lines · Zorro Lang
Quoted 26 lines · Naohiro Aota
Currently, we use "ls ... | sort -R | head -n1" (or tail) to choose a random file in a directory.It sorts the files with "ls", sort it randomly and pick the first line, which wastes the "ls" sort.
Also, using "sort -R | head -n1" is inefficient. For example, in a directory with 1000000 files, it takes more than 15 seconds to pick a file.
$ time bash -c "ls -U | sort -R | head -n 1 >/dev/null" bash -c "ls -U | sort -R | head -n 1 >/dev/null" 15.38s user 0.14s system 99% cpu 15.536 total$ time bash -c "ls -U | shuf -n 1 >/dev/null" bash -c "ls -U | shuf -n 1 >/dev/null" 0.30s user 0.12s system 138% cpu 0.306 totalSo, we should just use "ls -U" and "shuf -n 1" to choose a random file. Introduce
_random_file()helper to do it properly.Signed-off-by Naohiro Aota <[email protected]>--- common/rc | 7 +++++++ 1 file changed, 7 insertions(+)common/rc +0
-0common/rc _soak_loop_running() { · line 5231
Quoted 8 lines
common/rc +5
-0@@ -5224,6 +5224,13 @@ _soak_loop_running() { return 0 } +# Return a random file in a directory. A directory is *not* followed +# recursively. +_random_file() { + local basedir=$1 + echo "$basedir/$(ls -U $basedir | shuf -n 1)"I think the "1" can be the second argument, for we might want to get a random file list sometimes. For example:
local basedir=$1
local num=$2
local opt
Quoted 6 lines
if [ -n "$num" ];then
opt="-n $num"fi
echo "$basedir/$(ls -U $basedir | shuf $opt)"What do you think?
Hmm... nack my review point. Looks like this makes a simple change to be complicated, especially multiple output lines. I'll merge this patchset at first, then we can support that second argument If we need that feature in one day. Or if you're interested in it.
Thanks,
Zorro
Quoted 12 lines
Thanks,
ZorroQuoted 8 lines
common/rc +2
-0+} + init_rc ################################################################################Signature · 1 line
2.41.0
Re: [PATCH v3 1/3] common/rc: introduce _random_file() helper
Quoted 49 lines · Zorro Lang
Quoted 48 lines · Zorro Lang
Quoted 26 lines · Naohiro Aota
Currently, we use "ls ... | sort -R | head -n1" (or tail) to choose a random file in a directory.It sorts the files with "ls", sort it randomly and pick the first line, which wastes the "ls" sort.
Also, using "sort -R | head -n1" is inefficient. For example, in a directory with 1000000 files, it takes more than 15 seconds to pick a file.
$ time bash -c "ls -U | sort -R | head -n 1 >/dev/null" bash -c "ls -U | sort -R | head -n 1 >/dev/null" 15.38s user 0.14s system 99% cpu 15.536 total$ time bash -c "ls -U | shuf -n 1 >/dev/null" bash -c "ls -U | shuf -n 1 >/dev/null" 0.30s user 0.12s system 138% cpu 0.306 totalSo, we should just use "ls -U" and "shuf -n 1" to choose a random file. Introduce
_random_file()helper to do it properly.Signed-off-by Naohiro Aota <[email protected]>--- common/rc | 7 +++++++ 1 file changed, 7 insertions(+)common/rc +0
-0common/rc _soak_loop_running() { · line 5231
Quoted 8 lines
common/rc +5
-0@@ -5224,6 +5224,13 @@ _soak_loop_running() { return 0 } +# Return a random file in a directory. A directory is *not* followed +# recursively. +_random_file() { + local basedir=$1 + echo "$basedir/$(ls -U $basedir | shuf -n 1)"I think the "1" can be the second argument, for we might want to get a random file list sometimes. For example:
local basedir=$1
local num=$2
local optif [ -n "$num" ];then
opt="-n $num"fi
echo "$basedir/$(ls -U $basedir | shuf $opt)"
Quoted 6 lines
Quoted 1 line
What do you think?
Hmm... nack my review point. Looks like this makes a simple change to be complicated, especially multiple output lines. I'll merge this patchset at first, then we can support that second argument If we need that feature in one day. Or if you're interested in it.
Yeah, I think so too. Currently, we don't have "shuf -n N" usage where N >
1. Also, while there is a plain "shuf" usage, it is used with "find".
So, I agree we can extent the function when we need it.
Quoted 17 lines
Thanks,
ZorroQuoted 12 lines
Thanks,
ZorroQuoted 8 lines
common/rc +2
-0+} + init_rc ################################################################################Signature · 1 line
2.41.0
PATCH v3 2/3 fstests/btrfs: use _random_file() helper
In reply to Naohiro AotaUse _random_file() helper to choose a random file in a directory.
--- tests/btrfs/179 | 9 ++++----- tests/btrfs/192 | 14 ++++---------- 2 files changed, 8 insertions(+), 15 deletions(-)
tests/btrfs/179 +4 -5
@@ -45,8 +45,8 @@ fill_workload() # Randomly remove some files for every 5 loop if [ $(( $i % 5 )) -eq 0 ]; then - victim=$(ls "$SCRATCH_MNT/src" | sort -R | head -n1) - rm "$SCRATCH_MNT/src/$victim" + victim=$(_random_file "$SCRATCH_MNT/src") + rm "$victim" fi i=$((i + 1)) done
@@ -69,13 +69,12 @@ delete_workload() trap "wait; exit" SIGTERM while true; do sleep $((sleep_time * 2)) - victim=$(ls "$SCRATCH_MNT/snapshots" | sort -R | head -n1) + victim=$(_random_file "$SCRATCH_MNT/snapshots") if [ -z "$victim" ]; then # No snapshots available, sleep and retry later. continue fi - $BTRFS_UTIL_PROG subvolume delete \ - "$SCRATCH_MNT/snapshots/$victim" > /dev/null + $BTRFS_UTIL_PROG subvolume delete "$victim" > /dev/null done }
tests/btrfs/192 +4 -10
@@ -69,12 +69,6 @@ $BTRFS_UTIL_PROG subvolume create $SCRATCH_MNT/src > /dev/null mkdir -p $SCRATCH_MNT/snapshots mkdir -p $SCRATCH_MNT/src/padding -random_file() -{ - local basedir=$1 - echo "$basedir/$(ls $basedir | sort -R | tail -1)" -} - snapshot_workload() { trap "wait; exit" SIGTERM
@@ -85,9 +79,9 @@ snapshot_workload() $SCRATCH_MNT/src $SCRATCH_MNT/snapshots/$i \ > /dev/null # Do something small to make snapshots different - rm -f "$(random_file $SCRATCH_MNT/src/padding)" - rm -f "$(random_file $SCRATCH_MNT/src/padding)" - touch "$(random_file $SCRATCH_MNT/src/padding)" + rm -f "$(_random_file $SCRATCH_MNT/src/padding)" + rm -f "$(_random_file $SCRATCH_MNT/src/padding)" + touch "$(_random_file $SCRATCH_MNT/src/padding)" touch "$SCRATCH_MNT/src/padding/random_$RANDOM" i=$(($i + 1))
@@ -102,7 +96,7 @@ delete_workload() while true; do sleep 2 $BTRFS_UTIL_PROG subvolume delete \ - "$(random_file $SCRATCH_MNT/snapshots)" \ + "$(_random_file $SCRATCH_MNT/snapshots)" \ > /dev/null 2>&1 done }
Signature · 1 line
2.41.0
Re: [PATCH v3 2/3] fstests/btrfs: use _random_file() helper
LGTM
PATCH v3 3/3 btrfs/004: use shuf to shuffle the file lines
In reply to Naohiro AotaThe "sort -R" is slower than "shuf" even with the full output because "sort -R" actually sort them to group the identical keys.
$ time bash -c "seq 1000000 | shuf >/dev/null" bash -c "seq 1000000 | shuf >/dev/null" 0.18s user 0.03s system 104% cpu 0.196 total
$ time bash -c "seq 1000000 | sort -R >/dev/null" bash -c "seq 1000000 | sort -R >/dev/null" 19.61s user 0.03s system 99% cpu 19.739 total
Since the "find"'s outputs never be identical, we can just use "shuf" to optimize the selection.
--- tests/btrfs/004 | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
tests/btrfs/004 +1 -1
@@ -201,7 +201,7 @@ workout() cnt=0 errcnt=0 dir="$SCRATCH_MNT/$snap_name/" - for file in `find $dir -name f\* -size +0 | sort -R`; do + for file in `find $dir -name f\* -size +0 | shuf`; do extents=`_check_file_extents $file` ret=$? if [ $ret -ne 0 ]; then
Signature · 1 line
2.41.0
Re: [PATCH v3 3/3] btrfs/004: use shuf to shuffle the file lines
LGTM