Skip to contentSkip to conversation

fs/fat: calculate checksum in a loop instead of directly calculating

PATCH In review Alexander Kuleshov 3 participants 7 messages Feb 18, 2015 – Feb 24, 2015 VFAT/FAT/msdos filesystem

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 fs/fat: calculate checksum in a loop instead of directly calculating

---
 fs/fat/fat.h | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)
fs/fat/fat.h +5 -5
index 64e295e..1a5080b 100644
@@ -207,12 +207,12 @@ static inline void fat_save_attrs(struct inode *inode, u8 attrs)
 
 static inline unsigned char fat_checksum(const __u8 *name)
 {
+	u8 i;
 	unsigned char s = name[0];
-	s = (s<<7) + (s>>1) + name[1];	s = (s<<7) + (s>>1) + name[2];
-	s = (s<<7) + (s>>1) + name[3];	s = (s<<7) + (s>>1) + name[4];
-	s = (s<<7) + (s>>1) + name[5];	s = (s<<7) + (s>>1) + name[6];
-	s = (s<<7) + (s>>1) + name[7];	s = (s<<7) + (s>>1) + name[8];
-	s = (s<<7) + (s>>1) + name[9];	s = (s<<7) + (s>>1) + name[10];
+
+	for (i = 1; i < 11; i++)
+		s = (s << 7) + (s >> 1) + name[i];
+
 	return s;
 }
 
Signature · 1 line
2.3.0.80.g18d0fec
maintainer
#1 lore raw
Quoted 5 lines · Alexander Kuleshov

static inline unsigned char fat_checksum(const __u8 *name) {

fs/fat/fat.h +1 -1
+	u8 i;
 	unsigned char s = name[0];
-	s = (s<<7) + (s>>1) + name[1];	s = (s<<7) + (s>>1) + name[2];

fs/fat/fat.h static inline void fat_save_attrs(struct inode *inode, u8 attrs) · line 217

Quoted 10 lines
fs/fat/fat.h +4 -4
-	s = (s<<7) + (s>>1) + name[3];	s = (s<<7) + (s>>1) + name[4];
-	s = (s<<7) + (s>>1) + name[5];	s = (s<<7) + (s>>1) + name[6];
-	s = (s<<7) + (s>>1) + name[7];	s = (s<<7) + (s>>1) + name[8];
-	s = (s<<7) + (s>>1) + name[9];	s = (s<<7) + (s>>1) + name[10];
+
+	for (i = 1; i < 11; i++)
+		s = (s << 7) + (s >> 1) + name[i];
+
 	return s;
 }

When I wrote this, IIRC, there was measurable performance difference. All major gcc versions are enough smart now to optimize this?

Signature · 1 line
OGAWA Hirofumi <[email protected]>
#2 lore raw

Hello,

I tested two simple program with this (gcc-4.9.1)

Results are following:

time ./test_with_loop

real 0m0.001s
user 0m0.000s
sys 0m0.001s

And

time ./test_direct_calculation:

real 0m0.002s
user 0m0.000s
sys 0m0.001s

As you can see result almsot the same. Also i compared assembly output from two these programras and there are two notes:

1. Assembly output of the program with loop is half as much than program with directly rotation, but ofcourse we can't take it for rule here. Current version prepares stack and than just does:

addq $1, %rax
movzbl (%rax), %eax
addl %edx, %eax
movb %al, -1(%rbp)
movzbl -1(%rbp), %eax
rorb %al
movl %eax, %edx
movq -24(%rbp), %rax

11 times, but version with loop does the same but with cmp/jump.

Thank you.

2015-02-19 1:25 GMT+06:00 OGAWA Hirofumi <[email protected]>:

Quoted 22 lines
Quoted 5 lines · Alexander Kuleshov

static inline unsigned char fat_checksum(const __u8 *name) {

fs/fat/fat.h +1 -1
+     u8 i;
      unsigned char s = name[0];
-     s = (s<<7) + (s>>1) + name[1];  s = (s<<7) + (s>>1) + name[2];

fs/fat/fat.h static inline void fat_save_attrs(struct inode *inode, u8 attrs) · line 217

Quoted 10 lines
fs/fat/fat.h +4 -4
-     s = (s<<7) + (s>>1) + name[3];  s = (s<<7) + (s>>1) + name[4];
-     s = (s<<7) + (s>>1) + name[5];  s = (s<<7) + (s>>1) + name[6];
-     s = (s<<7) + (s>>1) + name[7];  s = (s<<7) + (s>>1) + name[8];
-     s = (s<<7) + (s>>1) + name[9];  s = (s<<7) + (s>>1) + name[10];
+
+     for (i = 1; i < 11; i++)
+             s = (s << 7) + (s >> 1) + name[i];
+
      return s;
 }

When I wrote this, IIRC, there was measurable performance difference. All major gcc versions are enough smart now to optimize this? --
OGAWA Hirofumi <[email protected]>

maintainer
#3 lore raw
Quoted 6 lines · Alexander Kuleshov

time ./test_with_loop

real 0m0.001s
user 0m0.000s
sys 0m0.001s

Quoted 7 lines

And

time ./test_direct_calculation:

real 0m0.002s
user 0m0.000s
sys 0m0.001s

Hm,

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

typedef unsigned char __u8;
typedef unsigned char u8;

#if 1
static inline unsigned char fat_checksum(const __u8 *name)

{
	unsigned char s = name[0];
	s = (s<<7) + (s>>1) + name[1];	s = (s<<7) + (s>>1) + name[2];
	s = (s<<7) + (s>>1) + name[3];	s = (s<<7) + (s>>1) + name[4];
	s = (s<<7) + (s>>1) + name[5];	s = (s<<7) + (s>>1) + name[6];
	s = (s<<7) + (s>>1) + name[7];	s = (s<<7) + (s>>1) + name[8];
	s = (s<<7) + (s>>1) + name[9];	s = (s<<7) + (s>>1) + name[10];
	return s;
}
#else
static inline unsigned char fat_checksum(const __u8 *name)
{
	unsigned char s = name[0];
	u8 i;
	for (i = 1; i < 11; i++)
		s = (s << 7) + (s >> 1) + name[i];
	return s;
}

#endif

static __attribute__ ((noinline)) int test(unsigned char *name)

{
	long i;
	for (i = 0; i < 100000000L; i++)
		name[i % 11] = fat_checksum(name);
	return name[0];
}

int main(int argc, char *argv[])

{
	printf("%u\n", test((unsigned char *)argv[1]));
	return 0;
}
  $ gcc --version
  gcc (Debian 4.9.1-19) 4.9.1
  Copyright (C) 2014 Free Software Foundation, Inc.
  This is free software; see the source for copying conditions.  There is NO
  warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  $ gcc -O2 -o c.inline c.c
  # change #if 1 => #if 0
  $ gcc -O2 -o c.loop c.c
  $ time ./c.inline aaaaaaaaaaa
  14

real 0m0.550s
user 0m0.548s
sys 0m0.000s

  $ time ./c.loop aaaaaaaaaaa
  14

real 0m0.901s
user 0m0.896s
sys 0m0.004s

This is my environment only? (gcc (Debian 4.9.1-19) 4.9.1)

Signature · 1 line
OGAWA Hirofumi <[email protected]>
#4 lore raw
Quoted 45 lines · OGAWA Hirofumi
Quoted 6 lines · Alexander Kuleshov

time ./test_with_loop

real 0m0.001s
user 0m0.000s
sys 0m0.001s

Quoted 7 lines

And

time ./test_direct_calculation:

real 0m0.002s
user 0m0.000s
sys 0m0.001s

Hm,

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

typedef unsigned char __u8;
typedef unsigned char u8;

#if 1
static inline unsigned char fat_checksum(const __u8 *name)

{
	unsigned char s = name[0];
	s = (s<<7) + (s>>1) + name[1];	s = (s<<7) + (s>>1) + name[2];
	s = (s<<7) + (s>>1) + name[3];	s = (s<<7) + (s>>1) + name[4];
	s = (s<<7) + (s>>1) + name[5];	s = (s<<7) + (s>>1) + name[6];
	s = (s<<7) + (s>>1) + name[7];	s = (s<<7) + (s>>1) + name[8];
	s = (s<<7) + (s>>1) + name[9];	s = (s<<7) + (s>>1) + name[10];
	return s;
}
#else
static inline unsigned char fat_checksum(const __u8 *name)
{
	unsigned char s = name[0];
	u8 i;
	for (i = 1; i < 11; i++)
		s = (s << 7) + (s >> 1) + name[i];
	return s;
}
Quoted 3 lines

#endif

static __attribute__ ((noinline)) int test(unsigned char *name)

You have to put
__attribute__((optimize("unroll-loops")))
here to unroll the loop inside the function:

static __attribute__ ((noinline))
__attribute__((optimize("unroll-loops")))
int test(unsigned char *name)

Quoted 30 lines
{
	long i;
	for (i = 0; i < 100000000L; i++)
		name[i % 11] = fat_checksum(name);
	return name[0];
}

int main(int argc, char *argv[])

{
	printf("%u\n", test((unsigned char *)argv[1]));
	return 0;
}
  $ gcc --version
  gcc (Debian 4.9.1-19) 4.9.1
  Copyright (C) 2014 Free Software Foundation, Inc.
  This is free software; see the source for copying conditions.  There is NO
  warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  $ gcc -O2 -o c.inline c.c
  # change #if 1 => #if 0
  $ gcc -O2 -o c.loop c.c
  $ time ./c.inline aaaaaaaaaaa
  14

real 0m0.550s
user 0m0.548s
sys 0m0.000s

Quoted 9 lines
  $ time ./c.loop aaaaaaaaaaa
  14

real 0m0.901s
user 0m0.896s
sys 0m0.004s

This is my environment only? (gcc (Debian 4.9.1-19) 4.9.1)

$ time ./c.inline aaaaaaaaaaa
14
real    0m0.743s
user    0m0.740s
sys     0m0.000s

Without __attribute__((optimize("unroll-loops"))) :

$ time ./c.loop aaaaaaaaaaa
14
real    0m1.482s
user    0m1.472s
sys     0m0.004s

With __attribute__((optimize("unroll-loops"))) :

$ time ./c.loop aaaaaaaaaaa
14
real    0m0.742s
user    0m0.740s
sys     0m0.000s

Best regards

Heinrich Schuchardt

maintainer
#5 lore raw
Quoted 24 lines · Heinrich Schuchardt

You have to put
__attribute__((optimize("unroll-loops")))
here to unroll the loop inside the function:

static __attribute__ ((noinline))
__attribute__((optimize("unroll-loops")))
int test(unsigned char *name)

$ time ./c.inline aaaaaaaaaaa
14
real    0m0.743s
user    0m0.740s
sys     0m0.000s

Without __attribute__((optimize("unroll-loops"))) :

$ time ./c.loop aaaaaaaaaaa
14
real    0m1.482s
user    0m1.472s
sys     0m0.004s
Quoted 8 lines

With __attribute__((optimize("unroll-loops"))) :

$ time ./c.loop aaaaaaaaaaa
14
real    0m0.742s
user    0m0.740s
sys     0m0.000s

This attribute has to be added to the caller, not fat_checksum()? I.e., we has to add it to all callers of fat_checksum()?

Well, this is interesting gcc optimize option though, maybe not worth to introduce this to kernel only for fatfs.

Thanks.

Signature · 1 line
OGAWA Hirofumi <[email protected]>
#6 lore raw
Quoted 31 lines · OGAWA Hirofumi
Quoted 29 lines · Heinrich Schuchardt

You have to put
__attribute__((optimize("unroll-loops")))
here to unroll the loop inside the function:

static __attribute__ ((noinline))
__attribute__((optimize("unroll-loops")))
int test(unsigned char *name)

$ time ./c.inline aaaaaaaaaaa
14
real    0m0.743s
user    0m0.740s
sys     0m0.000s

Without __attribute__((optimize("unroll-loops"))) :

$ time ./c.loop aaaaaaaaaaa
14
real    0m1.482s
user    0m1.472s
sys     0m0.004s

With __attribute__((optimize("unroll-loops"))) :

$ time ./c.loop aaaaaaaaaaa
14
Quoted 6 lines
Quoted 3 lines
real    0m0.742s
user    0m0.740s
sys     0m0.000s

This attribute has to be added to the caller, not fat_checksum()? I.e., we has to add it to all callers of fat_checksum()?

The attribute is applied to the declaration of the function in which you need loop unrolling.
https://gcc.gnu.org/onlinedocs/gcc-4.9.1/gcc/Attribute-Syntax.html

Quoted 3 lines

Well, this is interesting gcc optimize option though, maybe not worth to introduce this to kernel only for fatfs.

There is an effort to compile the Linux kernel with Clang. We should avoid new GCC specific items.

Best regards

Heinrich