Skip to contentSkip to conversation

use shuf to choose a random file

PATCH In review Naohiro Aota 3 participants 10 messages Aug 21, 2023 – Aug 28, 2023 Btrfs file system

lore
Share & tools
lore
#0 lore raw

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
#1 lore raw

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
index 5c4429ed0425..4d414955f6d9 100644
@@ -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
#3 lore raw

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

In reply to Naohiro Aota
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 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 +0 -0
index 5c4429ed0425..4d414955f6d9 100644

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
#4 lore raw

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 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 +0 -0
index 5c4429ed0425..4d414955f6d9 100644

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

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,
Zorro

Quoted 8 lines
common/rc +2 -0
+}
+
 init_rc
 
 ################################################################################
Signature · 1 line
2.41.0
#5 lore raw

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 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 +0 -0
index 5c4429ed0425..4d414955f6d9 100644

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)"

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,
Zorro

Quoted 12 lines

Thanks,
Zorro

Quoted 8 lines
common/rc +2 -0
+}
+
 init_rc
 
 ################################################################################
Signature · 1 line
2.41.0
#6 lore raw

PATCH v3 2/3 fstests/btrfs: use _random_file() helper

In reply to Naohiro Aota

Use _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
index 2f17c9f9fb4a..479667f05fd2 100755
@@ -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
index bcf14ebb8e3b..7324c9e39833 100755
@@ -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
#8 lore raw

PATCH v3 3/3 btrfs/004: use shuf to shuffle the file lines

In reply to 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.

---
 tests/btrfs/004 | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
tests/btrfs/004 +1 -1
index ea40dbf62880..78df6a3af6b1 100755
@@ -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