Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Go Data Structures (2009)

research.swtch.com

Post reply on HN
Print view View original

21–27 of 27 posts

Re: Go Data Structures (2009)

#21

Post by twotwotwo »

mitchty wrote: post #12
krakensden wrote: post #9

Earlier quoted context omitted.

That's kind of a big deal for a point release...

There is a good reason for it however. http://www.javaadvent.com/2012/12/changes-to-stringsubstring...

Here's more nitty-gritty from Oracle: http://mail.openjdk.java.net/pipermail/core-libs-dev/2012-Ma...

If I'm following, a Java string used to be a []char and offset/count ints, and this change let them drop those ints. You saved RAM if you had a lot of little strings, but paid for extra copying if you took lots of substrings.

Go slices/strings don't have a pointer to the "original" backing array, just a pointer to the first byte in this (sub)string. It doesn't need extra fields to do substrings by reference.

I think part of the technical reason for the different string headers is that the Java designers didn't want their GC to have to handle "internal pointers" into strings/objects (maybe for performance reasons?), whereas the Go designers decided to support 'em (maybe to support more C-like code in Go?).

Re: Go Data Structures (2009)

#22

Post by fauigerzigerk »

twotwotwo wrote: post #21
mitchty wrote: post #12

Earlier quoted context omitted.

There is a good reason for it however. http://www.javaadvent.com/2012/12/changes-to-stringsubstring...

Here's more nitty-gritty from Oracle: http://mail.openjdk.java.net/pipermail/core-libs-dev/2012-Ma... If I'm following, a Java string used to be a []char and offset/count ints, and this change let them drop those ints. You saved RAM if you had a lot of little strings, but paid for extra copying if you took lots of substrings. Go slices/strings don't have a pointer to the "original" backing array, just a pointer to th…

Go does not support internal pointers into strings. You have to use slicing for that.

Re: Go Data Structures (2009)

#23

Post by twotwotwo »

fauigerzigerk wrote: post #22
twotwotwo wrote: post #21

Earlier quoted context omitted.

Here's more nitty-gritty from Oracle: http://mail.openjdk.java.net/pipermail/core-libs-dev/2012-Ma... If I'm following, a Java string used to be a []char and offset/count ints, and this change let them drop those ints. You saved RAM if you had a lot of little strings, but paid for extra copying if you took lots of substrings. Go slices/strings don't have a pointer to the "original" backing array, just a pointer to th…

Go does not support internal pointers into strings. You have to use slicing for that.

Sorry, I mean that there's an internal pointer in Go's in-memory representation of the string, not that there's a naked byte pointer directly visible to the programmer.

Go's GC's support for internal pointers means it can use a pointer-and-length representation for substring references. Java's lack of support for them means its string representation needs a pointer to the start of the char array and a separate offset and count in order to do the same substring-reference trick. (And, I'm saying, that helps explain why Java and Go now do substrings differently.)

There are other places where Go's ability to use internal pointers is exposed more directly to the programmer: for example, Go lets you take the address of an array element or struct field and pass around the resulting pointer.

Re: Go Data Structures (2009)

#24

Post by fauigerzigerk »

twotwotwo wrote: post #23
fauigerzigerk wrote: post #22

Earlier quoted context omitted.

Go does not support internal pointers into strings. You have to use slicing for that.

Sorry, I mean that there's an internal pointer in Go's in-memory representation of the string, not that there's a naked byte pointer directly visible to the programmer. Go's GC's support for internal pointers means it can use a pointer-and-length representation for substring references. Java's lack of support for them means its string representation needs a pointer to the start of the char array and a separate offset…

>Go's GC's support for internal pointers means it can use a pointer-and-length representation for substring references

Only if the String class is implemented in pure Java, which it currently is. But it doesn't have to be that way. Oracle could go around the Java language features and implement the String class in native code just as Go does with several builtin types. You may be right that it would be more difficult to do than in Go because of garbage collector specifics.

But I guess the real issue is a philosophical one. Is it a good idea to let the standard library use features that are not available to users of the language?

Re: Go Data Structures (2009)

#25

Post by [deleted] »

rsc wrote: post #20
oofabz wrote: post #13

Earlier quoted context omitted.

The "new" keyword is practically unused in modern Go development, but is kept for backwards compatibility. The usual way to make a point is "p := &Point{}", without using any keyword.

Not true. I count "new" being used about half as often as "&Point{}" in the Go standard library. That's not "practically unused". g% cg -c -f 'g/go/src/pkg.*\.go' '\bnew\(' | total 2 1485 g% cg -c -f 'g/go/src/pkg.*\.go' '\&[A-Za-z0-9_.]+\{' | total 2 3051 g% cg -c -f 'g/go/src/pkg.*\.go' . | total 2 430482 g% So 430,482 non-blank lines of code, 1485 lines with new, 3051 lines that look like a struct pointer literal.

[deleted]

Re: Go Data Structures (2009)

#26

Post by twotwotwo »

fauigerzigerk wrote: post #24
twotwotwo wrote: post #23

Earlier quoted context omitted.

Sorry, I mean that there's an internal pointer in Go's in-memory representation of the string, not that there's a naked byte pointer directly visible to the programmer. Go's GC's support for internal pointers means it can use a pointer-and-length representation for substring references. Java's lack of support for them means its string representation needs a pointer to the start of the char array and a separate offset…

>Go's GC's support for internal pointers means it can use a pointer-and-length representation for substring references Only if the String class is implemented in pure Java, which it currently is. But it doesn't have to be that way. Oracle could go around the Java language features and implement the String class in native code just as Go does with several builtin types. You may be right that it would be more difficult…

I'm saying I think it would take GC rearchitecting for Java to be able use a pointer into the middle of the string in its internal String representation, because Java's GC, unlike Go's, is currently not built such that a pointer into the middle of anything keeps that thing "alive" for GC purposes; you have to have a pointer to the beginning. Sun made that choice that in hopes they could write a faster GC that way, I suspect.

Given that GC design, Go's two-word substring references (pointer into middle of string + count) wouldn't work; even if String were a builtin, with the no-internal-pointers GC design it would need to be at least three words (pointer to start of string, offset, count).

tl;dr of my larger point is--I think Java needed a few extra bytes/String to support substrings by reference because of how its GC works differently from Go's, and I think that explains why Java decided to remove its substring-by-reference trick while Go didn't. (And I'm not trying to say either way is worse, just trying to really grok why they're different.)

Re: Go Data Structures (2009)

#27

Post by trentmb »

rsc wrote: post #20
oofabz wrote: post #13

Earlier quoted context omitted.

The "new" keyword is practically unused in modern Go development, but is kept for backwards compatibility. The usual way to make a point is "p := &Point{}", without using any keyword.

Not true. I count "new" being used about half as often as "&Point{}" in the Go standard library. That's not "practically unused". g% cg -c -f 'g/go/src/pkg.*\.go' '\bnew\(' | total 2 1485 g% cg -c -f 'g/go/src/pkg.*\.go' '\&[A-Za-z0-9_.]+\{' | total 2 3051 g% cg -c -f 'g/go/src/pkg.*\.go' . | total 2 430482 g% So 430,482 non-blank lines of code, 1485 lines with new, 3051 lines that look like a struct pointer literal.

If I had to guess, I think they meant that anyone writing new code will avoid using 'new'.
Post reply on HN