2
\$\begingroup\$

I have a slice with ~2.1 million log message strings in it that I am parsing for regular expression matches. For any matches, I add it to a local slice and then return said slice.

func Search(re *regexp.Regexp, logs []string) []string {
    var lwg sync.WaitGroup
    var lresults = make([]string, 0)
    NumCPU := runtime.NumCPU() * 2
    var divided = make([][]string, 0)

    // Splits the log lines into sub slices based
    // on the number of CPUs available.
    ChunkSize := len(logs) / NumCPU
    if ChunkSize == 0 {
        ChunkSize = 0
    }
    if ChunkSize > 200000 {
        log.Warnf("There are %s lines of logs available. Searching may take awhile.", humanize.Comma(int64(len(logs))))
    }

    log.Debug("distributing the logs evenly.")
    for i := 0; i < len(logs); i += ChunkSize {
        end := i + ChunkSize
        if end > len(logs) {
            end = len(logs)
        }
        divided = append(divided, logs[i:end])
    }

    log.Debugf("searching through all logs for '%s'", regex)
    for ii := range divided {
        lwg.Add(2)
        total := len(divided[ii])
        mid := total / 2
        array := divided[ii]
        first := array[:mid]
        second := array[mid:]
        go func(s []string) {
            for _, xx := range s {
                if re.MatchString(xx) {
                    locker.Lock()
                    lresults = append(lresults, xx)
                    locker.Unlock()
                }
            }
            lwg.Done()
        }(first)
        go func(s []string) {
            for _, xx := range s {
                if re.MatchString(xx) {
                    locker.Lock()
                    lresults = append(lresults, xx)
                    locker.Unlock()
                }
            }
            lwg.Done()
        }(second)
    }
    lwg.Wait()
    log.Debugf("found %s matches.", humanize.Comma(int64(len(lresults))))

    return lresults
}

Is there a better/more efficient way to do this in Go? I know I could use channels, I'm just not sure how to implement it without hitting deadlocks (I'm still a beginner Go programmer).

\$\endgroup\$
  • \$\begingroup\$ This code is hard to review when it's incomplete. For instance, can you add relevant imports and more info about variables not declared here? \$\endgroup\$ – cat Feb 4 '16 at 0:34
  • \$\begingroup\$ locker is the only one I see missing, is there another, @cat? \$\endgroup\$ – rolfl Feb 4 '16 at 0:35
  • \$\begingroup\$ @rolfl The log package does not have any such exports Warnf and Debugf \$\endgroup\$ – cat Feb 4 '16 at 0:36
  • \$\begingroup\$ I don't have a humanize package in my standard library, it'd be nice if there were a link \$\endgroup\$ – cat Feb 4 '16 at 0:37
  • \$\begingroup\$ These things you say are true l-) point taken. I am part way through a review regardless. \$\endgroup\$ – rolfl Feb 4 '16 at 0:38
4
\$\begingroup\$

It's hard to review code that doesn't work per se, but I'll try my hand at a style review anyways.

func Search(re *regexp.Regexp, logs []string) []string

Nice method signature! But, exported function Search should have comment or be unexported. I trust there are docstrings in your code, right? That's valuable stuff, don't omit it here!

var lwg sync.WaitGroup
var lresults = make([]string, 0)
NumCPU := runtime.NumCPU() * 2
var divided = make([][]string, 0)

Personally, I find this kinda hard to read. You should do this instead:

var (
  lwg        sync.WaitGroup
  divided  = make([][]string, 0)
  lresults = make([]string, 0)
  NumCPU   = runtime.NumCPU() * 2
)

So much nicer. That's the handiwork of my IDE. The Go language distribution comes with a lot of code quality tools for readability and static analysis, and you should really use them often. (Every save, perhaps?)

// Splits the log lines into sub slices based
// on the number of CPUs available.

Yay, comments! /* multiline comments are more readable, though */.

ChunkSize := len(logs) / NumCPU
if ChunkSize == 0 {
    ChunkSize = 0
}

First of all, ChunkSize would ideally be declared in the var () block up there, because it seems like there are no other uses for NumCPU. Go is fastest when you are smart and efficient with your memory, so don't leave variables lying around for no reason.

Second, I find this pointless. Yes, I, too, cry at Go's lack of ternary operator, but it's missing for a reason. That being said, I don't understand why you are setting a variable to what it is... ?

if ChunkSize > 200000 {
    log.Warnf("There are %s lines of logs available. Searching may take awhile.", humanize.Comma(int64(len(logs))))
}

2e5 is more readable and more easily changeable later. Moreover, I don't understand the coersion to int64 here. Does humanize really only like int64? That seems lame.

for ii := range divided {
    lwg.Add(2)
    total := len(divided[ii])
    mid := total / 2
    array := divided[ii]
    first := array[:mid]
    second := array[mid:]
    go func(s []string) {
        for _, xx := range s {
            if re.MatchString(xx) {
                locker.Lock()
                lresults = append(lresults, xx)
                locker.Unlock()
            }
        }
        lwg.Done()
    }(first)
    go func(s []string) {
        for _, xx := range s {
            if re.MatchString(xx) {
                locker.Lock()
                lresults = append(lresults, xx)
                locker.Unlock()
            }
        }
        lwg.Done()
    }(second)
}

Whoa. Alright:

  1. array := divided[ii] is pointlessly cryptic, instead use for e, i := range divided {} and get the element and index that way -- it's cleaner.

  2. Naming. I understand it's hard; I struggle with it too: every coder does. But please, for the love of Go, either use i, index or int_theIndexOfTheFreakinFullyQualifiedStringObjectWeAreIteratingOn. ii is hard to pronounce, not rememberable... I hate it.

  3. As far as I can tell, these variables total, mid, first, second have exactly one use: right here in this loop. Remember what I said about Go being faster when you keep the work for the GC down to a minimum. I get it improves readability, but at a point, that stuff should just be inlined to keep the cache happy.

  4. I see zero difference between these go funcs, because they're identical. Ideally, you would assign it to a local var and call it on first and second.

  5. I can't run your code right now, which means I can't make it testable and I can't ask go race to take a look at it. What I can tell you, from a glance, is that you're accessing the same resources through two goroutines at once. The locker, assuming it does what it says on the tin, is a good thought, but you're still locking them at the same time and it's a recipe for disaster in the form of race conditions. See here, here, here, and the other results from the first page of google results on "avoid race condition golang".

return lresults

This could be a bare return if you put (lresults []string) in the signature, which would in my opinion improve readability both of the code and any generated docs.

\$\endgroup\$
  • \$\begingroup\$ You can downvote but you won't tell me how this post can be improved? Yes, I'm pretty new to CR, so tell me about all the ways I suck, please! \$\endgroup\$ – cat Feb 4 '16 at 1:53
4
\$\begingroup\$

The nice thing about channels is that they prevent deadlocks, not create them.

Some style things quickly, though. Things like:

NumCPU := runtime.NumCPU() * 2

NumCPU should start lowercase. Method variables should always be, as they are never exported.

I will duplicate what @cat says here... what's this? (It's a WTF in case you were wondering...):

if ChunkSize == 0 {
    ChunkSize = 0
}

Then, about your code, it is really confusing why you split the data in to chunks based on the number of cores you have (actually, twice as many), and then you loop through the chunks, and for each loop, bizarrely, you split each chunk in half again, and process each half in a separate routine. If you have 4 real cores, you split the data 8 ways, and each of those 8 ways spins off 2 routines - making the whole thing a 16-way split on a 4-core machine. That's not technically, horrible but if that's what you want, just do that with runtime.NumCPU() * 4 instead of runtime.NumCPU() * 2....

It's all just.... odd.

Now, you have a locker that's created outside the function (I assume). This is a problem because if your code is called multiple times concurrently, then you will have two different result slices being locked by one lock. The amount of locking you do is really concerning too.... why lock for every record? I would accumulate each goroutine's results in a local slice, then, when the routine is complete, I would add them all to the (locked) result slice.

All told, I would probably make life simple with:

func Search(re *regexp.Regexp, logs []string) []string {

    // oversubscribe to the CPU's intentionally
    parallel := runtime.NumCPU() * 2

    // Splits the log lines into sub slices based
    // on the number of CPUs available.
    chunkSize := len(logs) / parallel

    // Don't be silly on how small partitions get
    if chunkSize < parallel {
        chunkSize = len(logs)
    }

    if chunkSize > 200000 {
        log.Warnf("There are %s lines of logs available. Searching may take awhile.", humanize.Comma(int64(len(logs))))
    }

    complete := sync.WaitGroup()
    collector := make(chan []string, parallel)

    log.Debug("distributing the logs evenly.")
    for start := 0; start < len(logs); start += chunkSize {
        end := start + chunkSize
        if end > len(logs) {
            end = len(logs)
        }

        complete.Add(1)
        go func() {
            defer complete.Done()
            found := []string{}
            for _, log := range logs[start:end] {
                if re.MatchString(xx) {
                    found = append(found, log)
                }
            }
            // publish our results to a channel (has internal locking)
            collector <- found
        }()
    }

    go func() {
        // when all data is checked, close the collector.
        complete.Wait()
        close(collector)
    }()

    lresult := []string{}
    for data := range collector {
        lresult = append(lresult, data...)
    }

    return lresults
}
\$\endgroup\$
  • \$\begingroup\$ Is there a chance that the second goroutine's complete.Wait() will fall through before any of the searching goroutines have a chance to call complete.Add(1), causing a panic when the latter try to send to a closed channel with collector <- found? \$\endgroup\$ – David Harkness Mar 4 '16 at 19:31
  • \$\begingroup\$ @DavidHarkness - good catch, yes. The complete.Add(1) should be done before the goroutine starts. \$\endgroup\$ – rolfl Mar 4 '16 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.