I remember being shocked to find that every GOTO (and even a NEXT) would do a linear search for the right line number starting from the beginning of the program image.

They really, actively did not care about performance. Manifestly, it was the right choice for the time, place, and circumstances, but it is hard to see how, today.