5
\$\begingroup\$

I started learning Go a few months ago and am trying to shake the rust off after a project took me out of the Go world for several weeks. I'd appreciate a code review on this flood fill algorithm I wrote for practice.

Specifically I'm looking for points on any code I've written that is unidiomatic in Go, and of course any glaring mistakes that my manual testing didn't catch. Performance is a more minor concern. I'm sure I can tell each node where it came from to improve performance by ~25%, but that's more trouble than it's worth for a little practice code.

package fill

type OrderedPair struct {
    x, y int
}

var wg sync.WaitGroup

func FloodFill(graph [][]int, origin OrderedPair) []OrderedPair {
    val := graph[origin.y][origin.x]
    length := 0
    for _, row := range graph {
        length += len(row)
    }
    q := make(chan OrderedPair, length)
    q <- origin

    seen := make(map[OrderedPair]struct{})

    for {
        select {
        case op := <-q:
            if _, found := seen[op]; found {
                continue
            } else {
                seen[op] = struct{}{}
            }
            wg.Add(4)
            for _, mods := range [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} {
                go func(xmod, ymod int) {
                    newx := op.x + xmod
                    newy := op.y + ymod
                    if 0 <= newy && newy < len(graph) && 0 <= newx && newx < len(graph[newy]) {
                        if graph[newy][newx] == val {
                            q <- OrderedPair{newx, newy}
                        }
                    }
                    wg.Done()
                }(mods[0], mods[1])
            }
            wg.Wait()
        default:
            result := make([]OrderedPair, 0, len(seen))
            for key := range seen {
                result = append(result, key)
            }
            return result
        }
    }
}

Particularly I'm not a big fan of the

for {
    select {
    case DO SOMETHING:
        // ...
    default:
        // wrap up the function and return
    }
}

I would much rather my default case break me out of the infinite loop so I handle the cleanup and return on the parent level, but it seems a break in a select statement just breaks the select. Any better way to handle that?

I'd also like to generalize the function if possible. Since I'm not using any sort of fuzzy-match and I'm giving back []OrderedPair regardless, I should be able to operate on a graph [][]interface{} but the mechanics of that aren't clear to me (I can't pass in a concrete [][]int or [][]string anymore. Do I have to go through the reflect package? That seems like a pain, but might be out of scope for CR)

\$\endgroup\$
1
  • \$\begingroup\$ in reality the queue need never be larger than the longest perimeter of points inside the graph (not the area of the graph!), but it seems to me that calculating that would be much harder than just allocating a larger queue that can't be exceeded \$\endgroup\$
    – Adam Smith
    Mar 22 '16 at 20:24
1
\$\begingroup\$

Have you tried to benchmark your solution against a simpler non-parallel one?

go-routines are really cheap, but that's relative to real threads. Your use of the go-routines at such a granular level, and the heavy use of the channel as a queue, are bound to be causing all sorts of memory contention.

I suspect that if you just process the whole lot in a single routine, with a simple slice, that things will be a whole lot faster.... and simpler.

So, turn q in to a make([]OrderedPair, 0, length) (a slice with capactiy for possibly everything), and then append flood-candidates to that.

Your seen map should also possibly be a map[OrderedPair]bool instead of map[OrderedPair]struct{}. It makes the logic easier later... instead of:

if _, found := seen[op]; found {
    continue

you can instead have:

if seen[op] {
    continue

Also, there's no reason to have an 'else' clause to that if. The continue breaks the code block scope, so the else is redundant.

More completely, the following:

        if _, found := seen[op]; found {
            continue
        } else {
            seen[op] = struct{}{}
        }

should be:

if seen[op] {
    continue
}
seen[op] = true

The WaitGroup is also a problem. It should be declared inside the function.... but really, you don't want goroutines here anyway. Promise.

The up-down-left-right slice could also be simplified a bunch too without the routines. No need for the closures and shadow-copies, and so on.

Instead of the seen map, I would consider having a boolean 2-D slice that matches the same dimensions as the input data (screw the memory footprint, worst-case memory footprint is probably less than worst-case memory for the map anyway)

All told, I would reduce the code to something like:

type OrderedPair struct {
    x, y int
}

var mods = [...]struct {
    x, y int
}{
    {-1, 0}, {1, 0}, {0, -1}, {0, 1},
}


func FloodFill(graph [][]int, origin OrderedPair) []OrderedPair {
    val, ok := graph[origin.y][origin.x]
    if !ok {
        // origin is not part of the graph!?!?!?!?
        return nil
    }

    seen := make([][]bool, len(graph))
    for i, row := range graph {
        seen[i] = make([]bool, len(row))
    }

    // let go sort out the appended size.
    fill := []OrderedPair{}

    // go will shuffle memory too when adding/removing items from q
    q := []OrderedPair{origin}

    for len(q) > 0 {

        // shift the q
        op := q[0]
        q = q[1:]

        if seen[op.y][op.x] {
            continue
        }

        seen[op.y][op.x] = true
        fill = append(fill, op)

        for _, mod := range mods {
            newx := op.x + mod.x
            newy := op.y + mod.y
            if 0 <= newy && newy < len(graph) && 0 <= newx && newx < len(graph[newy]) {
                if graph[newy][newx] == val {
                    q = append(q, OrderedPair{newx, newy})
                }
            }
        }
    }
    return fill
}
\$\endgroup\$

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.