[PATCH v2 0/3] use shuf to choose a random file

[PATCH v2 0/3] use shuf to choose a random file

[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. 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".

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 |  4 ++--
 tests/btrfs/192 | 14 ++++----------
 4 files changed, 14 insertions(+), 13 deletions(-)

-- 
2.41.0

[PATCH v2 1/3] common/rc: introduce _random_file() helper

[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 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.

Signed-off-by: Naohiro Aota <naohiro.aota@wdc.com>
---
 common/rc | 7 +++++++
 1 file changed, 7 insertions(+)

diff --git a/common/rc b/common/rc
index 5c4429ed0425..2bdda30f497a 100644
--- a/common/rc
+++ b/common/rc
@@ -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
+	ls -U "${basedir}" | shuf -n 1
+}
+
 init_rc
 
 ################################################################################
-- 
2.41.0

[PATCH v2 2/3] fstests/btrfs: use _random_file() helper

[Naohiro Aota]

Use _random_file() helper to choose a random file in a directory.

Signed-off-by: Naohiro Aota <naohiro.aota@wdc.com>
---
 tests/btrfs/179 |  4 ++--
 tests/btrfs/192 | 14 ++++----------
 2 files changed, 6 insertions(+), 12 deletions(-)

diff --git a/tests/btrfs/179 b/tests/btrfs/179
index 2f17c9f9fb4a..33a854d70401 100755
--- a/tests/btrfs/179
+++ b/tests/btrfs/179
@@ -45,7 +45,7 @@ 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)
+			victim=$(_random_file "$SCRATCH_MNT/src")
 			rm "$SCRATCH_MNT/src/$victim"
 		fi
 		i=$((i + 1))
@@ -69,7 +69,7 @@ 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
diff --git a/tests/btrfs/192 b/tests/btrfs/192
index bcf14ebb8e3b..7324c9e39833 100755
--- a/tests/btrfs/192
+++ b/tests/btrfs/192
@@ -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
 }
-- 
2.41.0

[PATCH v2 3/3] btrfs/004: use shuf to shuffle the file lines

[Naohiro Aota]

The "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.

Signed-off-by: Naohiro Aota <naohiro.aota@wdc.com>
---
 tests/btrfs/004 | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/tests/btrfs/004 b/tests/btrfs/004
index ea40dbf62880..78df6a3af6b1 100755
--- a/tests/btrfs/004
+++ b/tests/btrfs/004
@@ -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
-- 
2.41.0

Re: [PATCH v2 0/3] use shuf to choose a random file

[Naohiro Aota]

On Mon, Aug 21, 2023 at 03:37:01PM +0900, Naohiro Aota wrote:
> 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".

Please discard this version. The _random_file() helper doesn't have the
base directory prefixed. So, the btrfs/192 didn't work well. I'll revise it
soon.