Как Go ищет метод в interface?

При первом присваивании типа интерфейсу runtime делает сопоставление методов — проходит по списку методов интерфейса и ищет соответствующие методы типа. Оба списка отсортированы, поэтому сопоставление за O(n+m). Результат сохраняется в itab. При последующих вызовах — просто indirect call через указатель в itab, без поиска. Это довольно быстро.