Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

image/color: Palette.Index can be optimized #43756

Closed
zj360202 opened this issue Jan 18, 2021 · 4 comments
Closed

image/color: Palette.Index can be optimized #43756

zj360202 opened this issue Jan 18, 2021 · 4 comments
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance

Comments

@zj360202
Copy link

zj360202 commented Jan 18, 2021

What did you do?

image/color

func (p Palette) Index(c Color) int {
	// A batch version of this computation is in image/draw/draw.go.

	cr, cg, cb, ca := c.RGBA()
	ret, bestSum := 0, uint32(1<<32-1)
	for i, v := range p {
		vr, vg, vb, va := v.RGBA()
		sum := sqDiff(cr, vr) + sqDiff(cg, vg) + sqDiff(cb, vb) + sqDiff(ca, va)
		if sum < bestSum {
			if sum == 0 {
				return i
			}
			ret, bestSum = i, sum
		}
	}
	return ret
}

is very slowly
image size 1366x768 --> cost > 2s

What did you expect to see?

func (p Palette) Index(c color.Color) int {
	// A batch version of this computation is in image/draw/draw.go.

	var mod uint8 = 51
	var splitNum = 255 / mod + 1
	cr, cg, cb, ca := c.RGBA()
	cr8, cg8, cb8, ca8 := uint8(cr), uint8(cg), uint8(cb), uint8(ca)
	ri, gi, bi, ai := cr8/mod, cg8/mod, cb8/mod, ca8/mod
	rm, gm, bm, am := cr8%mod, cg8%mod, cb8%mod, ca8%mod
	if rm > mod/2{
		ri += 1
	}
	if gm > mod/2 {
		gi += 1
	}
	if bm > mod/2 {
		bi += 1
	}
	if am > mod/2 {
		ai += 1
	}
	//ret := int(ri * 36 + gi * 6 + bi)
	ret := int(ri * splitNum * splitNum + gi * 6 + bi)
	return ret
}

will be faster
image size 1366x768 --> cost < 100ms

What did you see instead?

@seankhliao seankhliao changed the title image.Palette get Index is very slowly image/color: Palette.Index can be optimized Jan 18, 2021
@seankhliao seankhliao added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Jan 18, 2021
@seankhliao
Copy link
Member

@zj360202 please feel free to send in a PR / CL with the proposed improvements

@zj360202
Copy link
Author

@seankhliao OK, I will send a PR

@gopherbot
Copy link

Change https://golang.org/cl/287892 mentions this issue: image/color: Palette.Index can be optimized

@nigeltao
Copy link
Contributor

nigeltao commented Feb 2, 2021

As I mentioned on https://golang.org/cl/287892, we can't assume that p (the receiver for the Palette.Index method) is the Netscape 6x6x6 color cube.

@nigeltao nigeltao closed this as completed Feb 2, 2021
@golang golang locked and limited conversation to collaborators Feb 2, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Projects
None yet
5 participants