strings,bytes: ToLower(), ToUpper() by using bitwise operator

When the string consists of only ASCII characters, we can convert lower case to upper case using bitwise operators. Bitwise operators are more efficient than using addition or subtraction.

go/src/strings/strings.go

Lines 616 to 625 in 3e67f46

    
           for i := 0; i < len(s); i++ { 
        
           	c := s[i] 
        
           	if 'a' <= c && c <= 'z' { 
        
           		c -= 'a' - 'A' 
        
           		if pos < i { 
        
           			b.WriteString(s[pos:i]) 
        
           		} 
        
           		b.WriteByte(c) 
        
           		pos = i + 1 
        
           	}

For example, in Rust, they used bitwise operator to implement the converter.

https://github.com/rust-lang/rust/blob/c387f012b14a3d64e0d580b7ebe65e5325bcf822/library/core/src/num/mod.rs#L576-L579

I propose that we replace the addition and subtraction operators with bitwise operators in the following four places.

go/src/strings/strings.go

Lines 616 to 625 in 3e67f46

    
           for i := 0; i < len(s); i++ { 
        
           	c := s[i] 
        
           	if 'a' <= c && c <= 'z' { 
        
           		c -= 'a' - 'A' 
        
           		if pos < i { 
        
           			b.WriteString(s[pos:i]) 
        
           		} 
        
           		b.WriteByte(c) 
        
           		pos = i + 1 
        
           	}

go/src/strings/strings.go

Lines 656 to 666 in 3e67f46

    
           for i := 0; i < len(s); i++ { 
        
           	c := s[i] 
        
           	if 'A' <= c && c <= 'Z' { 
        
           		c += 'a' - 'A' 
        
           		if pos < i { 
        
           			b.WriteString(s[pos:i]) 
        
           		} 
        
           		b.WriteByte(c) 
        
           		pos = i + 1 
        
           	} 
        
           }

go/src/bytes/bytes.go

Lines 638 to 652 in 3e67f46

    
           if isASCII { // optimize for ASCII-only byte slices. 
        
           	if !hasLower { 
        
           		// Just return a copy. 
        
           		return append([]byte(""), s...) 
        
           	} 
        
           	b := bytealg.MakeNoZero(len(s)) 
        
           	for i := 0; i < len(s); i++ { 
        
           		c := s[i] 
        
           		if 'a' <= c && c <= 'z' { 
        
           			c -= 'a' - 'A' 
        
           		} 
        
           		b[i] = c 
        
           	} 
        
           	return b 
        
           }

go/src/bytes/bytes.go

Lines 669 to 682 in 3e67f46

    
           if isASCII { // optimize for ASCII-only byte slices. 
        
           	if !hasUpper { 
        
           		return append([]byte(""), s...) 
        
           	} 
        
           	b := bytealg.MakeNoZero(len(s)) 
        
           	for i := 0; i < len(s); i++ { 
        
           		c := s[i] 
        
           		if 'A' <= c && c <= 'Z' { 
        
           			c += 'a' - 'A' 
        
           		} 
        
           		b[i] = c 
        
           	} 
        
           	return b 
        
           }

@ksw2000

@ksw2000 I don't see in what way this is change the api or behavior, if this is purely an internal change you don't need a proposal and can just submit a patch. 🙂

Sorry, this is my first time creating an issue for Golang, and I'm not sure what type of issue to use. Can you please tell me what type of issue I should use for an issue like this or could I just pull request directly?

I am so sorry for my mistake. I will make sure to learn how to use it correctly next time.

Taking this out of the proposal milestone as it doesn't involve API changes.

@ksw2000

@ksw2000
You only need a proposal when you're trying to make API changes or language changes, you can just send a CL directly for this without making a proposal since what you're intended to do here doesn't involve API or language changes.

See golang proposal for details.

@panjf2000

@panjf2000
Thank you very much for your detailed explanation. I will send a CL directly. Should I close this issue?

I think you should, when you submit your CL don't forget to post benchmark results using benchstat. 🙂

Leave this issue and add a line Fixes #64361 in the commit message of your CL.

I'm not sure I buy the premise that bitwise operators are any faster than adding or subtracting.
They are all 1 cycle operations on modern processors.

After testing, I found that the improvement is negligible. I will close this issue. Thank you for the discussion.

I'm not sure I buy the premise that bitwise operators are any faster than adding or subtracting.
They are all 1 cycle operations on modern processors.

This makes the code branchless which helps a auto vectorizers, so this does not apply to gc.
Without counting for memory bandwidth using back of the napkin math, should be 16x faster (since we can load and store 16 bytes per cycle) instead of 1.

@joroppo Branchless would be great if you can do it. How would you do that here, exactly?

你好！我是JYQin！您的邮件已经收到！！！

I'm fairly confident branch-less would be slower here since it would need to generate masks. But SIMD with masks would be faster than SISD.
I get what you mean now, I thought you could fuse the anding of the masks you have to do in SIMD with the anding of the bits, but however then you need to move the mask to the 6th bit first so it's not actually any faster.

After trying it to be sure, I'm not able to measure anything.
I had trouble making the compiler generate the most efficient comparison and bit handling so trying in assembly (SISD) branches, cmov and SETcc with rsh they are all bottlenecked on writing to memory anyway and run at the same speed.

In src/strings/strings.go

ToUpper

by add/sub operation (original method)

func ToUpper(s string) string {
	isASCII, hasLower := true, false
	for i := 0; i < len(s); i++ {
		c := s[i]
		if c >= utf8.RuneSelf {
			isASCII = false
			break
		}
		hasLower = hasLower || ('a' <= c && c <= 'z')
	}

	if isASCII { // optimize for ASCII-only strings.
		if !hasLower {
			return s
		}
		var (
			b   Builder
			pos int
		)
		b.Grow(len(s))
		for i := 0; i < len(s); i++ {
			c := s[i]
			if 'a' <= c && c <= 'z' {
				c -= 'a' - 'A'
				if pos < i {
					b.WriteString(s[pos:i])
				}
				b.WriteByte(c)
				pos = i + 1
			}
		}
		if pos < len(s) {
			b.WriteString(s[pos:])
		}
		return b.String()
	}
	return Map(unicode.ToUpper, s)
}

by binary operation

// ToUpper returns s with all Unicode letters mapped to their upper case.
func ToUpper(s string) string {
	isASCII, hasLower := true, false
	for i := 0; i < len(s); i++ {
		c := s[i]
		if c >= utf8.RuneSelf {
			isASCII = false
			break
		}
		hasLower = hasLower || ('a' <= c && c <= 'z')
	}

	if isASCII { // optimize for ASCII-only strings.
		if !hasLower {
			return s
		}
		var (
			b   Builder
			pos int
		)
		b.Grow(len(s))
		for i := 0; i < len(s); i++ {
			c := s[i]
			if 'a' <= c && c <= 'z' {
				c ^= 0b100000
				if pos < i {
					b.WriteString(s[pos:i])
				}
				b.WriteByte(c)
				pos = i + 1
			}
		}
		if pos < len(s) {
			b.WriteString(s[pos:])
		}
		return b.String()
	}
	return Map(unicode.ToUpper, s)
}

goos: linux
goarch: amd64
pkg: strings
cpu: Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz
                                                                      │ oldToUpper.txt │           newToUpper.txt           │
                                                                      │     sec/op     │   sec/op     vs base               │
ToUpper/#00-8                                                             4.046n ±  1%   4.046n ± 1%       ~ (p=0.643 n=10)
ToUpper/ONLYUPPER-8                                                       14.39n ±  1%   14.39n ± 1%       ~ (p=0.565 n=10)
ToUpper/abc-8                                                             42.16n ±  5%   43.84n ± 8%       ~ (p=0.529 n=10)
ToUpper/AbC123-8                                                          86.77n ±  7%   85.29n ± 8%       ~ (p=0.247 n=10)
ToUpper/azAZ09_-8                                                         85.95n ±  6%   82.30n ± 6%       ~ (p=0.078 n=10)
ToUpper/longStrinGwitHmixofsmaLLandcAps-8                                 329.6n ±  7%   316.5n ± 9%       ~ (p=0.447 n=10)
ToUpper/RENAN_BASTOS_93_AOSDAJDJAIDJAIDAJIaidsjjaidijadsjiadjiOOKKO-8     593.3n ±  7%   588.6n ± 7%       ~ (p=0.971 n=10)
ToUpper/longɐstringɐwithɐnonasciiⱯchars-8                                 522.8n ±  8%   501.9n ± 3%  -4.00% (p=0.005 n=10)
ToUpper/ɐɐɐɐɐ-8                                                           515.1n ± 13%   465.4n ± 9%       ~ (p=0.105 n=10)
ToUpper/a\u0080\U0010ffff-8                                               184.1n ± 13%   178.0n ± 3%       ~ (p=0.436 n=10)
geomean                                                                   105.9n         103.3n       -2.43%

ToLower

by add/sub operation (original method)

// ToLower returns s with all Unicode letters mapped to their lower case.
func ToLower(s string) string {
	isASCII, hasUpper := true, false
	for i := 0; i < len(s); i++ {
		c := s[i]
		if c >= utf8.RuneSelf {
			isASCII = false
			break
		}
		hasUpper = hasUpper || ('A' <= c && c <= 'Z')
	}

	if isASCII { // optimize for ASCII-only strings.
		if !hasUpper {
			return s
		}
		var (
			b   Builder
			pos int
		)
		b.Grow(len(s))
		for i := 0; i < len(s); i++ {
			c := s[i]
			if 'A' <= c && c <= 'Z' {
				c += 'a' - 'A'
				if pos < i {
					b.WriteString(s[pos:i])
				}
				b.WriteByte(c)
				pos = i + 1
			}
		}
		if pos < len(s) {
			b.WriteString(s[pos:])
		}
		return b.String()
	}
	return Map(unicode.ToLower, s)
}

by binary operation

// ToLower returns s with all Unicode letters mapped to their lower case.
func ToLower(s string) string {
	isASCII, hasUpper := true, false
	for i := 0; i < len(s); i++ {
		c := s[i]
		if c >= utf8.RuneSelf {
			isASCII = false
			break
		}
		hasUpper = hasUpper || ('A' <= c && c <= 'Z')
	}

	if isASCII { // optimize for ASCII-only strings.
		if !hasUpper {
			return s
		}
		var (
			b   Builder
			pos int
		)
		b.Grow(len(s))
		for i := 0; i < len(s); i++ {
			c := s[i]
			if 'A' <= c && c <= 'Z' {
				c |= 0b100000
				if pos < i {
					b.WriteString(s[pos:i])
				}
				b.WriteByte(c)
				pos = i + 1
			}
		}
		if pos < len(s) {
			b.WriteString(s[pos:])
		}
		return b.String()
	}
	return Map(unicode.ToLower, s)
}

goos: linux
goarch: amd64
pkg: strings
cpu: Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz
                                                                      │ oldToLower.txt │            newToLower.txt            │
                                                                      │     sec/op     │    sec/op     vs base                │
ToUpper/#00-8                                                             4.035n ±  1%   4.042n ±  1%        ~ (p=0.315 n=10)
ToUpper/ONLYUPPER-8                                                       14.38n ±  0%   14.38n ±  1%        ~ (p=0.640 n=10)
ToUpper/abc-8                                                             43.23n ±  8%   43.16n ±  5%        ~ (p=0.971 n=10)
ToUpper/AbC123-8                                                          83.76n ±  6%   81.94n ±  9%        ~ (p=0.436 n=10)
ToUpper/azAZ09_-8                                                         80.98n ±  6%   84.15n ± 10%        ~ (p=0.063 n=10)
ToUpper/longStrinGwitHmixofsmaLLandcAps-8                                 313.2n ±  8%   308.4n ± 10%        ~ (p=0.393 n=10)
ToUpper/RENAN_BASTOS_93_AOSDAJDJAIDJAIDAJIaidsjjaidijadsjiadjiOOKKO-8     592.4n ±  7%   497.6n ± 26%  -16.00% (p=0.043 n=10)
ToUpper/longɐstringɐwithɐnonasciiⱯchars-8                                 504.5n ±  9%   520.5n ±  6%        ~ (p=0.481 n=10)
ToUpper/ɐɐɐɐɐ-8                                                           516.0n ±  9%   490.2n ±  6%        ~ (p=0.089 n=10)
ToUpper/a\u0080\U0010ffff-8                                               178.2n ± 18%   175.2n ±  6%        ~ (p=0.895 n=10)
geomean                                                                   103.9n         101.7n         -2.09%

Navigation Menu

Repository navigation

strings,bytes: ToLower(), ToUpper() by using bitwise operator #64361

ToUpper

ToLower

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

	for i := 0; i < len(s); i++ {
	c := s[i]
	if 'a' <= c && c <= 'z' {
	c -= 'a' - 'A'
	if pos < i {
	b.WriteString(s[pos:i])
	}
	b.WriteByte(c)
	pos = i + 1
	}

	if isASCII { // optimize for ASCII-only byte slices.
	if !hasLower {
	// Just return a copy.
	return append([]byte(""), s...)
	}
	b := bytealg.MakeNoZero(len(s))
	for i := 0; i < len(s); i++ {
	c := s[i]
	if 'a' <= c && c <= 'z' {
	c -= 'a' - 'A'
	}
	b[i] = c
	}
	return b
	}

	if isASCII { // optimize for ASCII-only byte slices.
	if !hasUpper {
	return append([]byte(""), s...)
	}
	b := bytealg.MakeNoZero(len(s))
	for i := 0; i < len(s); i++ {
	c := s[i]
	if 'A' <= c && c <= 'Z' {
	c += 'a' - 'A'
	}
	b[i] = c
	}
	return b
	}

strings,bytes: ToLower(), ToUpper() by using bitwise operator #64361

Description

Activity

Jorropo commented on Nov 23, 2023

ksw2000 commented on Nov 23, 2023

panjf2000 commented on Nov 23, 2023

panjf2000 commented on Nov 23, 2023

ksw2000 commented on Nov 23, 2023

Jorropo commented on Nov 23, 2023

panjf2000 commented on Nov 23, 2023

randall77 commented on Nov 23, 2023

ksw2000 commented on Nov 23, 2023

Jorropo commented on Nov 23, 2023

randall77 commented on Nov 24, 2023

jiangbajin commented on Nov 24, 2023

Jorropo commented on Nov 24, 2023

Jorropo commented on Nov 24, 2023

ksw2000 commented on Nov 24, 2023

ToUpper

ToLower

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions