On: Go Data Structures: Interfaces (2009)

[philippta]

Because the latter would incur a hidden O(n) computation.

[rollcat → philippta]

It's not just the O(n), you must think of interface{} as a pair (concreteType, pointerToMutableData). It's a can of worms, allocating n*2 word-sized objects for each rune is just the surface layer - strings in particular are immutable.

I think Go does the right thing to make this allocation and assignment explicit, you may be a little less surprised with how the program actually behaves. https://go.dev/play/p/PzuBpM66VX2

[TheDong → philippta]

since when has that stopped go? “[]rune(someString)” is O(n) and quite inobvious

The O(n) loop is here: https://github.com/golang/go/blob/215de81513286c010951624243...

[foldr → TheDong]

It’s obvious that this is O(n), no? You’re casting something immutable to something mutable, so it has to be copied.

[debugnik → foldr]

And decoding subsequences of UTF-8 code units (bytes) into Unicode scalars (runes), which also forces a copy.

But why did Go pick the same syntax for cheap conversions and expensive ones, though? I'd expect this to be a standard function, not a type conversion.

[foldr → debugnik]

Don't all conversions require copying the value at the level of the language semantics? You can cast a float to an int, but you can't assign an integer value to a float variable (leaving aside whatever optimizations the compiler might make). Casting a float to an int is only cheap because a float is a fixed size. So it seems unsurprising to me that casting a larger value results in a proportionally larger copy.

[TheDong → foldr]

Most conversions are things like casts to enum types or aliases I think, which never are O(n), like:

    dur := time.Second * time.Duration(2)
    
    headers := http.Header(map[string][]string{})

    httpDir := http.Dir(filepath.Join(parts...))

In all of these cases, it's just a type-cast which is zero-cost, and I think that's what makes it feel surprising that casting between strings/runes specifically incurs more significant computation than any other cast.

[foldr → TheDong]

All of those are copies and hence O(n) in the size of the value copied. This is hidden somewhat because your examples use constants and literals. (As numeric constants aren’t typed in Go the first example arguably doesn’t involve a copy, but the rest do.)