block: optimise bvec_iter_advance()

bvec_iter_advance() is quite popular, but compilers fail to do proper alias analysis and optimise it good enough. The assembly is checked for gcc 9.2, x86-64.

- remove @iter->bi_size from min(...), as it's always less than @bytes. Modify at the beginning and forget about it.

- the compiler isn't able to collapse memory dependencies and remove writes in the loop. Help it by explicitely using local vars.

Signed-off-by Pavel Begunkov <[email protected]>

---
 include/linux/bvec.h | 23 ++++++++++++++---------
 1 file changed, 14 insertions(+), 9 deletions(-)

include/linux/bvec.h +14 -9

index a032f01e928c..7b2f05faae14 100644
@@ -87,26 +87,31 @@ struct bvec_iter_all {
 static inline bool bvec_iter_advance(const struct bio_vec *bv,
 		struct bvec_iter *iter, unsigned bytes)
 {
+	unsigned int done = iter->bi_bvec_done;
+	unsigned int idx = iter->bi_idx;
+
 	if (WARN_ONCE(bytes > iter->bi_size,
 		     "Attempted to advance past end of bvec iter\n")) {
 		iter->bi_size = 0;
 		return false;
 	}
 
+	iter->bi_size -= bytes;
+
 	while (bytes) {
-		const struct bio_vec *cur = bv + iter->bi_idx;
-		unsigned len = min3(bytes, iter->bi_size,
-				    cur->bv_len - iter->bi_bvec_done);
+		const struct bio_vec *cur = bv + idx;
+		unsigned int len = min(bytes, cur->bv_len - done);
 
 		bytes -= len;
-		iter->bi_size -= len;
-		iter->bi_bvec_done += len;
-
-		if (iter->bi_bvec_done == cur->bv_len) {
-			iter->bi_bvec_done = 0;
-			iter->bi_idx++;
+		done += len;
+		if (done == cur->bv_len) {
+			idx++;
+			done = 0;
 		}
 	}
+
+	iter->bi_idx = idx;
+	iter->bi_bvec_done = done;
 	return true;
 }
 

Signature · 1 line

2.24.0

The loop can be simplified a bit further, as done has to be 0 once we go beyond the current bio_vec. See below for the simplified version.

I also check if bi_size became zero so we can skip the rest of the calculations in that case. If we want to preserve the current behavior of updating iter->bi_idx and iter->bi_bvec_done even if bi_size is going to become zero, the loop condition should change to

		while (bytes && bytes >= cur->bv_len)

to ensure that we don't try to access past the end of the bio_vec array.

include/linux/bvec.h +13 -12

index a032f01e928c..380d188dfbd2 100644
@@ -87,25 +87,26 @@ struct bvec_iter_all {
 static inline bool bvec_iter_advance(const struct bio_vec *bv,
 		struct bvec_iter *iter, unsigned bytes)
 {
+	unsigned int idx = iter->bi_idx;
+	const struct bio_vec *cur = bv + idx;
+
 	if (WARN_ONCE(bytes > iter->bi_size,
 		     "Attempted to advance past end of bvec iter\n")) {
 		iter->bi_size = 0;
 		return false;
 	}
 
-	while (bytes) {
-		const struct bio_vec *cur = bv + iter->bi_idx;
-		unsigned len = min3(bytes, iter->bi_size,
-				    cur->bv_len - iter->bi_bvec_done);
-
-		bytes -= len;
-		iter->bi_size -= len;
-		iter->bi_bvec_done += len;
-
-		if (iter->bi_bvec_done == cur->bv_len) {
-			iter->bi_bvec_done = 0;
-			iter->bi_idx++;
+	iter->bi_size -= bytes;
+	if (iter->bi_size != 0) {
+		bytes += iter->bi_bvec_done;
+		while (bytes >= cur->bv_len) {
+			bytes -= cur->bv_len;
+			idx++;
+			cur++;
 		}
+
+		iter->bi_idx = idx;
+		iter->bi_bvec_done = bytes;
 	}
 	return true;
 }

Quoted 4 lines · Arvind Sankar

The loop can be simplified a bit further, as done has to be 0 once we go beyond the current bio_vec. See below for the simplified version.

Thanks for the suggestion! I thought about it, and decided to not for several reasons. I prefer to not fine-tune and give compilers more opportunity to do their job. And it's already fast enough with modern architectures (MOVcc, complex addressing, etc).

Also need to consider code clarity and the fact, that this is inline, so should be brief and register-friendly.

Quoted 7 lines

I also check if bi_size became zero so we can skip the rest of the calculations in that case. If we want to preserve the current behavior of updating iter->bi_idx and iter->bi_bvec_done even if bi_size is going to become zero, the loop condition should change to

		while (bytes && bytes >= cur->bv_len)

Probably, it's better to leave it in a consistent state. Shouldn't be a problem, but never know when and who will screw it up.

Quoted 6 lines · Pavel Begunkov

Quoted 4 lines · Arvind Sankar

The loop can be simplified a bit further, as done has to be 0 once we go beyond the current bio_vec. See below for the simplified version.

Quoted 8 lines

Thanks for the suggestion! I thought about it, and decided to not for several reasons. I prefer to not fine-tune and give compilers more opportunity to do their job. And it's already fast enough with modern architectures (MOVcc, complex addressing, etc).

Also need to consider code clarity and the fact, that this is inline, so should be brief and register-friendly.

It should be more register-friendly, as it uses fewer variables, and I think it's easier to see what the loop is doing, i.e. that we advance one bio_vec per iteration: in the existing code, it takes a bit of thinking to see that we won't spend more than one iteration within the same bio_vec.

I don't see this as fine-tuning, rather simplifying the code. I do agree that it's not going to make much difference for performance of the loop itself, as the most common case I think is that we either stay in the current bio_vec or advance by one.

Quoted 6 lines

Quoted 6 lines

I also check if bi_size became zero so we can skip the rest of the calculations in that case. If we want to preserve the current behavior of updating iter->bi_idx and iter->bi_bvec_done even if bi_size is going to become zero, the loop condition should change to

Quoted 5 lines

Quoted 1 line

		while (bytes && bytes >= cur->bv_len)

Probably, it's better to leave it in a consistent state. Shouldn't be a problem, but never know when and who will screw it up.

The WARN_ONCE case does leave it inconsistent, though that's not supposed to happen, so less of a pitfall there.

Quoted 16 lines · Arvind Sankar

Quoted 6 lines · Pavel Begunkov

Quoted 4 lines · Arvind Sankar

The loop can be simplified a bit further, as done has to be 0 once we go beyond the current bio_vec. See below for the simplified version.

Quoted 8 lines

Thanks for the suggestion! I thought about it, and decided to not for several reasons. I prefer to not fine-tune and give compilers more opportunity to do their job. And it's already fast enough with modern architectures (MOVcc, complex addressing, etc).

Also need to consider code clarity and the fact, that this is inline, so should be brief and register-friendly.

Quoted 5 lines

It should be more register-friendly, as it uses fewer variables, and I think it's easier to see what the loop is doing, i.e. that we advance one bio_vec per iteration: in the existing code, it takes a bit of thinking to see that we won't spend more than one iteration within the same bio_vec.

Yeah, may be. It's more the matter of preference then. I don't think it's simpler, and performance is entirely depends on a compiler and input. But, that's rather subjective and IMHO not worth of time.

Anyway, thanks for thinking this through!

Quoted 23 lines · Pavel Begunkov

Quoted 16 lines · Arvind Sankar

Quoted 6 lines · Pavel Begunkov

Quoted 4 lines · Arvind Sankar

The loop can be simplified a bit further, as done has to be 0 once we go beyond the current bio_vec. See below for the simplified version.

Quoted 8 lines

Thanks for the suggestion! I thought about it, and decided to not for several reasons. I prefer to not fine-tune and give compilers more opportunity to do their job. And it's already fast enough with modern architectures (MOVcc, complex addressing, etc).

Also need to consider code clarity and the fact, that this is inline, so should be brief and register-friendly.

Quoted 5 lines

It should be more register-friendly, as it uses fewer variables, and I think it's easier to see what the loop is doing, i.e. that we advance one bio_vec per iteration: in the existing code, it takes a bit of thinking to see that we won't spend more than one iteration within the same bio_vec.

Quoted 6 lines

Yeah, may be. It's more the matter of preference then. I don't think it's simpler, and performance is entirely depends on a compiler and input. But, that's rather subjective and IMHO not worth of time.

Anyway, thanks for thinking this through!

You don't find listing 1 simpler than listing 2? It does save one register, as it doesn't have to keep track of done independently from bytes. This is always going to be the case unless the compiler can eliminate done by transforming Listing 2 into Listing 1. Unfortunately, even if it gets much smarter, it's unlikely to be able to do that, because they're equivalent only if there is no overflow, so it would need to know that bytes + iter->bi_bvec_done cannot overflow, and that iter->bi_bvec_done must be smaller than cur->bv_len initially.

Listing 1:

	bytes += iter->bi_bvec_done;
	while (bytes) {
		const struct bio_vec *cur = bv + idx;

		if (bytes < cur->bv_len)
			break;
		bytes -= cur->bv_len;
		idx++;
	}

	iter->bi_idx = idx;
	iter->bi_bvec_done = bytes;

Listing 2:

	while (bytes) {
		const struct bio_vec *cur = bv + idx;
		unsigned int len = min(bytes, cur->bv_len - done);

		bytes -= len;
		done += len;
		if (done == cur->bv_len) {
			idx++;
			done = 0;
		}
	}

	iter->bi_idx = idx;
	iter->bi_bvec_done = done;

Quoted 69 lines · Arvind Sankar

Quoted 23 lines · Pavel Begunkov

Quoted 16 lines · Arvind Sankar

Quoted 6 lines · Pavel Begunkov

Quoted 4 lines · Arvind Sankar

The loop can be simplified a bit further, as done has to be 0 once we go beyond the current bio_vec. See below for the simplified version.

Quoted 8 lines

Thanks for the suggestion! I thought about it, and decided to not for several reasons. I prefer to not fine-tune and give compilers more opportunity to do their job. And it's already fast enough with modern architectures (MOVcc, complex addressing, etc).

Also need to consider code clarity and the fact, that this is inline, so should be brief and register-friendly.

Quoted 5 lines

It should be more register-friendly, as it uses fewer variables, and I think it's easier to see what the loop is doing, i.e. that we advance one bio_vec per iteration: in the existing code, it takes a bit of thinking to see that we won't spend more than one iteration within the same bio_vec.

Quoted 6 lines

Yeah, may be. It's more the matter of preference then. I don't think it's simpler, and performance is entirely depends on a compiler and input. But, that's rather subjective and IMHO not worth of time.

Anyway, thanks for thinking this through!

You don't find listing 1 simpler than listing 2? It does save one register, as it doesn't have to keep track of done independently from bytes. This is always going to be the case unless the compiler can eliminate done by transforming Listing 2 into Listing 1. Unfortunately, even if it gets much smarter, it's unlikely to be able to do that, because they're equivalent only if there is no overflow, so it would need to know that bytes + iter->bi_bvec_done cannot overflow, and that iter->bi_bvec_done must be smaller than cur->bv_len initially.

Listing 1:

    bytes += iter->bi_bvec_done;
    while (bytes) {
        const struct bio_vec *cur = bv + idx;

        if (bytes < cur->bv_len)
            break;
        bytes -= cur->bv_len;
        idx++;
    }

    iter->bi_idx = idx;
    iter->bi_bvec_done = bytes;

Listing 2:

    while (bytes) {
        const struct bio_vec *cur = bv + idx; unsigned int len = min(bytes, cur->bv_len - done);

        bytes -= len;
        done += len;
        if (done == cur->bv_len) {
            idx++;
            done = 0;
        }
    }

Quoted 2 lines

    iter->bi_idx = idx;
    iter->bi_bvec_done = done;

Have yet to take a closer look (and benchmark) and the patches and the generated code, but fwiw I do agree that case #1 is easier to read.

Quoted 70 lines · Jens Axboe

Quoted 69 lines · Arvind Sankar

Quoted 23 lines · Pavel Begunkov

Quoted 16 lines · Arvind Sankar

Quoted 6 lines · Pavel Begunkov

Quoted 4 lines · Arvind Sankar

The loop can be simplified a bit further, as done has to be 0 once we go beyond the current bio_vec. See below for the simplified version.

Quoted 8 lines

Thanks for the suggestion! I thought about it, and decided to not for several reasons. I prefer to not fine-tune and give compilers more opportunity to do their job. And it's already fast enough with modern architectures (MOVcc, complex addressing, etc).

Also need to consider code clarity and the fact, that this is inline, so should be brief and register-friendly.

Quoted 5 lines

It should be more register-friendly, as it uses fewer variables, and I think it's easier to see what the loop is doing, i.e. that we advance one bio_vec per iteration: in the existing code, it takes a bit of thinking to see that we won't spend more than one iteration within the same bio_vec.

Quoted 6 lines

Yeah, may be. It's more the matter of preference then. I don't think it's simpler, and performance is entirely depends on a compiler and input. But, that's rather subjective and IMHO not worth of time.

Anyway, thanks for thinking this through!

You don't find listing 1 simpler than listing 2? It does save one register, as it doesn't have to keep track of done independently from bytes. This is always going to be the case unless the compiler can eliminate done by transforming Listing 2 into Listing 1. Unfortunately, even if it gets much smarter, it's unlikely to be able to do that, because they're equivalent only if there is no overflow, so it would need to know that bytes + iter->bi_bvec_done cannot overflow, and that iter->bi_bvec_done must be smaller than cur->bv_len initially.

Listing 1:

     bytes += iter->bi_bvec_done;
     while (bytes) {
         const struct bio_vec *cur = bv + idx;

         if (bytes < cur->bv_len)
             break;
         bytes -= cur->bv_len;
         idx++;
     }

     iter->bi_idx = idx;
     iter->bi_bvec_done = bytes;

Listing 2:

     while (bytes) {
         const struct bio_vec *cur = bv + idx;
         unsigned int len = min(bytes, cur->bv_len - done);

         bytes -= len;
         done += len;
         if (done == cur->bv_len) {
             idx++;
             done = 0;
         }
     }

Quoted 7 lines

Quoted 2 lines

     iter->bi_idx = idx;
     iter->bi_bvec_done = done;

Have yet to take a closer look (and benchmark) and the patches and the generated code, but fwiw I do agree that case #1 is easier to read.

Ok, ok, I'm not keen on bike-shedding. I'll resend a simplified version