Moved to skeeto/scratch/misc
Last active
August 29, 2021 22:22
-
-
Save skeeto/d8b18fb4663f4a282e8c0db252a70faf to your computer and use it in GitHub Desktop.
quniq
As soon as I saw the DNS lookup in your program I remembered having
looked at it before. I even commented on it back then:
https://old.reddit.com/r/commandline/comments/aaopyq/freq_display_the_frequency_of_each_line_in_a_file/
In that thread I had written yet another histogram tool that I
completely forgot about. (I like quniq a lot more.)
I suspect there's something wrong with your tests and that the time is
dominated by something essentially outside the test (file seek, etc.) In
my tests the time difference is far more dramatic: quniq is consistently
4x faster than freq, and "sort|uniq -c" (GNU, LC_ALL=C) is consistently
1.5x faster than freq. We'd should expect quniq to be faster than freq
because it's not a fair comparison: quniq doesn't do any sorting.
In my tests I can shave off about 10% of the run time of freq by using
buffered output (i.e. bufio.NewWriter(os.Stdout)) in the output()
function. Right now you're writing unbuffered output via fmt.Printf().
That's one system call per line, which you can verify with strace. This
is a very common mistake in Go programs since, unlike C, it's unbuffered
by default.
Other than that you're really just running into the performance
limitations of the gc implementation of Go. There's nothing you can do
without departing from what makes Go Go. At this point in time you'll
never be able to beat the performance of C or C++ with Go.
On some paths you're doing lots of string transformations when certain
features are enabled. These might be faster if you use []byte rather
than string and do the manipulations in-place as much as possible. Note:
bytes.ToLower() is not in-place.
Since you mentioned it, I don't expect either -s and -w to impact the
performance characteristics of your program. The extra data isn't even
part of any LOAD segment and the exact same number of pages are mapped
at load time.
While I'm here some comments on your program in general:
Run gofmt on your code. If following the standard coding style doesn't
interest you on its own, then at least check out goimports, a superset
of gofmt that also manages your imports. It's wonderful!
Your input and output functions are very configurable, taking lots of
parameters. Lots of parameters, and especially bool parameters, are a
code smell in any language. Consider creating a configuration struct to
hold all this information.
Further, there's a lot of redundancy with the way options combine. With
optional features disabled, do this. If it's case-insensitive do this.
If using only a substring, do this. If it's case-insensitive and only
uses a substring, do this. Every time you add a new feature, the
possibilities double.
To solve this, consider composition. Create a "filter" interface, and
then implement a filter that converts its input to lowercase. Then
another filter that takes a substring of its input. At run time
construct a chain of filters based on the user's configuration. Each new
option only requires one new filter implementation.
The catch is that this would probably cost some performance from calling
through all these interfaces. Your current implementation has the
advantage of static filter configurations, at the cost of combinatorial
explosion in the source. But Go isn't really about being as fast as
possible, and good design is generally preferred over a small
performance boost. That's why the standard library uses interfaces and
reflection in so much.
You can do a similar thing with output filters to compose various,
orthogonal options.
Hi Chris,
This is some really great feedback! I really appreciate it. I have a habit of switching between vim and VSCode, which automatically uses gofmt. I need to get into the habit of running it when using vim or find some type of plug-in which does this on save.
I am going to experiment with buffered output and using byte slices instead of strings -- those are excellent ideas.
Could you please give me a good GitHub example that is not too complex but implements a configuration struct and a "filter" interface? I am not too familiar with these paradigms. You also mentioned good design is generally preferred over a small performance boost. My code is definitely ugly (but works). I would love to make it cleaner and more maintainable.
Thanks again,
-John
Could you please give me a good GitHub example that is not too complex but implements a configuration struct
https://github.com/skeeto/passphrase2pgp/blob/870b0a4/passphrase2pgp.go#L83
That struct is filled out by the option parser and gets passed around the program so that the different components can access the parts of the configuration they need. If I add or remove an option I don't have to change all the call sites to add/remove parameters/arguments.
and a "filter" interface?
Here are two approaches: functional and interface. I'll start with the one I prefer:
package main
import (
"fmt"
"strings"
)
type filter func(string) string
func identity(s string) string {
return s
}
func chain(a, b filter) filter {
return func(s string) string {
return b(a(s))
}
}
func substring(beg, end int) filter {
return func(s string) string {
return s[beg:end]
}
}
func reverse(s string) string {
r := []rune(s)
for i, j := 0, len(r)-1; i < len(r)/2; i, j = i+1, j-1 {
r[i], r[j] = r[j], r[i]
}
return string(r)
}
func main() {
f := filter(identity)
f = chain(f, strings.ToLower)
f = chain(f, substring(0, 4))
f = chain(f, reverse)
fmt.Println(f("FooBar"))
}Note how I start with the identity filter, then chain on new filters dynamically. Your option parser could append new filters as it parses arguments, so that the order of filters depends on the order the of arguments. Also notice how I could use strings.ToLower directly because it was already a filter.
Here's the interface version:
package main
import (
"fmt"
"strings"
)
type filter interface {
Transform(string) string
}
type identity struct{}
func (_ *identity) Transform(s string) string {
return s
}
type chain [2]filter
func (c *chain) Transform(s string) string {
return c[1].Transform(c[0].Transform(s))
}
type lower struct{}
func (_ *lower) Transform(s string) string {
return strings.ToLower(s)
}
type substring struct{ beg, end int }
func (x *substring) Transform(s string) string {
return s[x.beg:x.end]
}
type reverse struct{}
func (_ *reverse) Transform(s string) string {
r := []rune(s)
for i, j := 0, len(r)-1; i < len(r)/2; i, j = i+1, j-1 {
r[i], r[j] = r[j], r[i]
}
return string(r)
}
func main() {
f := filter(&identity{})
f = &chain{f, &lower{}}
f = &chain{f, &substring{0, 4}}
f = &chain{f, &reverse{}}
fmt.Println(f.Transform("FooBar"))
}Quite a bit more verbose, but potentially more flexible if you filters become more complex. In the function version the substring filter captured its configuration in a closure. In the interface version it's stored on a struct.
Thanks again for another great reply - and what a cool reverse() function! I also noticed that your passphrase code imports your own optparse library. The configuration struct idea seems pretty straight forward.
The functional version it easier for me to follow. The chaining concept looks really useful. I am going to experiment with it. OTOH, the interface version seems syntactically cumbersome and is harder for me to follow. I think ease of use is going to win out for me vs potential flexibility.
Yeah, I really don't like Go's flag package, neither the API nor UI.
GNU-style options are just too good to give up, and all the other option
parsing packages I could find with better UIs still had poor APIs. So I
filled that gap with nullprogram.com/x/optparse. It's essentially a port
of my C library of the same name: https://github.com/skeeto/optparse
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Hi skeeto,
I wonder if you remember your post:
I just learned how to compile C code under Windows using the command line version of the C compiler, cl.
This was nice to be able to compile within a Docker container and thus not having to install VS. Since I just
figured out how to do this, I thought I would compare them and share the results.
I was testing
quniqagainst my Go program found here:Benchmarks
Here are some benchmarks under Linux and Windows 10.
File size: of test-file 'c' is 4,969,612,772 bytes
It has 259,373,437 lines, 372,762 are unique
File created under Windows with this command:
dir /s/b c:\ | sed "s,\\,\n,g" > cUnder Windows, test-file was located on a RAM disk
Under AWS Linux EC2, test-file was located on a NVMe disk
freqwas compiled on both platforms with:go build -ldflags="-s -w"quniqwas compiled under Linux with:gcc -O3 quniq.c -o quniqUnder Windows, it was compiled and linked with the same options that zlib uses:
cl -c -nologo -MD -W3 -O2 -Oy- -Zi quniq.clink -nologo -debug -incremental:no -opt:ref quniq.objResults
I have not done enough experimentation to draw any conclusions other than they run about the same speed, while
quniquses less memory thanfreq.If you have the time, I would be interested in knowing if there is any way that you see to speed up my Go program.
Direct Link:
https://github.com/jftuga/freq/blob/master/freq.go
Thanks,
-John