Address Operators for Map Index

[Popog]

Is there a reason the language spec is such that array indexing
operation are addressable, but map indexing operations are not?

Every time I've used a map[x] T, I've had to change it to a map[x] *T,
just so I can use methods, and it's rather frustrating.

Is there some problem with making map indexing addressable?

[Steven]

Yes there is. In an array, the elements exist and stay in the same place for the entire existence of the array. ie. &array[5] will point to the sixth element of array for as long as array exists (the array can't cease to exist while you have a pointer to or into it).

For maps, their contents and representations in memory are constantly changing and they are rearranged and resized behind the scenes. If you have a pointer to an element that is moved or removed, then your pointer is no longer valid. Elements don't exist for the lifetime of the map, or even stay in the same spot, so getting a pointer to one will likely cause problems.

[Popog]

Couldn't the implementation of maps be changed to be node based, thus
extending their lifetime? Then the nodes could be kept alive if a
pointer to their data was retained.

A problem with a particular implementation shouldn't prevent the
language specification from being more intuitive.

If this discussion has already been hashed out (pardon the pun)
somewhere, can I get a link to it?

[Alexander Surma]

> Couldn't the implementation of maps be changed to be node based, thus
> extending their lifetime? Then the nodes could be kept alive if a
> pointer to their data was retained.

I'm not familiar with the actual implementation, but I guess using a node
based adressing system would slow access down the bigger the map is. And
speed is one of the main arguments for using a map, isn't it?
Also, what's so bad with using *T?
I do see your point, that this is in fact somewhat counter-intuitive,
but you can seldom have it both ways, intuitive and efficient.
In my opinion, Go has reached an unmatched level being intuitive and
still keeping the binaries efficient (and this being a system
programming language, the focus is without doubt on effiency).

Surma

[Popog]

On Jul 30, 7:12 am, Alexander Surma <alexander.su...@googlemail.com>
wrote:

> I'm not familiar with the actual implementation, but I guess using a node
> based adressing system would slow access down the bigger the map is. And
> speed is one of the main arguments for using a map, isn't it?

My intuition is that it wouldn't be a significant slow down, as hash
tables in general exhibit poor locality of reference (assuming they're
using has tables), and since the cost of moving to a node based
solution is locality of reference (in addition to a small memory
cost), it shouldn't be too bad.

Also, it is more important for built in types to be intuitive and
consistent than it is for them to be fast. They're supposed to be all-
purpose, minimum hassle. If someone needs an ultra fast data
structure, they should use something from containers or writing it
themselves.

> Also, what's so bad with using *T?

This situation happens to me a lot: http://pastebin.com/tZ123V4L

It's really annoying to have to "temp := A(); N[i] = &temp"
everywhere. I could make A return a *T, but that makes little sense in
a lot of situations. I could wrap A with a different function that
does the whole "&temp" shenanigans, but that's kludgy and time
consuming if there are multiple functions like A that need to be
wrapped.

IMHO, *T is a hack solution for programs that are slapped together.

[John Asmuth]

I believe the reason you can't do "x := &A()" or "x := &myMap[aKey]"
is that what is returned from them is stored in a temporary register
with no proper heap/stack memory address, and it has nothing to do
with, for instance, the underlying implementation of map.

- John

[roger peppe]

On 30 July 2010 16:05, Popog <pop...@gmail.com> wrote:
> This situation happens to me a lot: http://pastebin.com/tZ123V4L
>
> It's really annoying to have to "temp := A(); N[i] = &temp"
> everywhere. I could make A return a *T, but that makes little sense in
> a lot of situations. I could wrap A with a different function that
> does the whole "&temp" shenanigans, but that's kludgy and time
> consuming if there are multiple functions like A that need to be
> wrapped.

the easiest solution is just to use either T everywhere or
*T everywhere. if B has no side effects, then it could be
a method on T without loss of generality.

as for the constructor A, i quite like this pattern:

func (t *T) A() *T {
t.foo = 3
t.bar = "hello"
return t
}

that way you get to choose whether to use T or *T.

e.g.

N[i] = new(T).A()

vs.

(&somestruct.t).A()

[David Roundy]

On Fri, Jul 30, 2010 at 11:05 AM, Popog <pop...@gmail.com> wrote:
>> Also, what's so bad with using *T?
>
> This situation happens to me a lot: http://pastebin.com/tZ123V4L
>
> It's really annoying to have to "temp := A(); N[i] = &temp"
> everywhere. I could make A return a *T, but that makes little sense in
> a lot of situations.

I'm confused as to what situations having A() return a *T wouldn't
make sense. Could you give an example?
--
David Roundy

[Popog]

On Jul 30, 8:16 am, John Asmuth <jasm...@gmail.com> wrote:
> I believe the reason you can't do "x := &A()" or "x := &myMap[aKey]"
> is that what is returned from them is stored in a temporary register
> with no proper heap/stack memory address, and it has nothing to do
> with, for instance, the underlying implementation of map.
>
> - John

That is simply the reason for the direct implementation, which could
"easily" be changed.

[Popog]

On Jul 30, 8:21 am, roger peppe <rogpe...@gmail.com> wrote:
> the easiest solution is just to use either T everywhere or
> *T everywhere.
>

> as for the constructor A, i quite like this pattern:
>
> func (t *T) A() *T {
>     t.foo = 3
>     t.bar = "hello"
>     return t
>
> }

A() wasn't necessarily a direct constructor, just an arbitrary
function, but I do like that pattern. However, I don't think that
forcing someone to use a pointer where it doesn't make sense is the
right solution. Pointers are supposed to have a purpose.

[Russ Cox]

> A() wasn't necessarily a direct constructor, just an arbitrary
> function, but I do like that pattern. However, I don't think that
> forcing someone to use a pointer where it doesn't make sense is the
> right solution. Pointers are supposed to have a purpose.

what purpose did you have in making
your method take a pointer receiver?
if you gave it a value receiver you'd be
able to call it on a map index expression
just fine.

russ

[Popog]

On Jul 30, 9:25 am, Russ Cox <r...@golang.org> wrote:
> what purpose did you have in making
> your method take a pointer receiver?
> if you gave it a value receiver you'd be
> able to call it on a map index expression
> just fine.
>
> russ

B() modifies the receiver's fields. Why does everyone question the
specifics of my Gedankenexperiment?

Yes, I know, the next suggestion is going to be, why not use a value
receiver and do M[i] = M[i].B(). Because it's stupid. To the person
who was thinking of suggesting this, answer me this, why are there
pointer receivers at all? You could just say j = j.method() for every
method that needed to modify j.

[David Roundy]

On Fri, Jul 30, 2010 at 12:46 PM, Popog <pop...@gmail.com> wrote:
> Why does everyone question the specifics of my Gedankenexperiment?

Because programming is about solving problems, and you failed to
describe one, and instead just described what you wanted to do. If
you want useful advice, you need to describe your problem with
sufficient accuracy that we can understand why the natural go-like
solution doesn't make sense for you.
--
David Roundy

[Cory Mainwaring]

Sorry, vague questions get vague answers. The first two were specific. Then the next question was: "Why do I have to use a pointer when there isn't a purpose to using it?" Russ then responded with what your purpose was, so that he could answer with either an alternative to using a pointer in that situation (not M[i] = M[i].B()) or saying that a pointer would fulfill that purpose and giving reasons why it does. Be careful of vague questions, they frustrate everyone, including yourself.

[Popog]

On Jul 30, 10:09 am, David Roundy <roun...@physics.oregonstate.edu>
wrote:

The theoretical code is unimportant, it was merely meant to give a
context for my frustration, I apologize for doing so as I appear to
have derailed my own thread.

Now, back to the matter at hand. For what purpose are maps a lesser
built-in container in this regard? Would some problem arise a map
indexing operation was granted addressability? Is there some inherent
gain from not granting maps addressable indexing?

I kindly request that we all hold of on questioning what adding
addressability will add until these questions are answered first. I'd
like to go over what we'd lose before we go over what we might gain.

[Russ Cox]

On Fri, Jul 30, 2010 at 10:45, Popog <pop...@gmail.com> wrote:
> Now, back to the matter at hand. For what purpose are maps a lesser
> built-in container in this regard? Would some problem arise a map
> indexing operation was granted addressability? Is there some inherent
> gain from not granting maps addressable indexing?

This has already been answered (by stev...@gmail.com).

Russ

[Popog]

On Jul 30, 11:55 am, Russ Cox <r...@golang.org> wrote:
> This has already been answered (by steven...@gmail.com).
>
> Russ

Having already responded to Steven's answer to my question, I inquire
are there any further problems with changing it or explicit benefits
to not changing it?

Along those lines, is there much validity to Surma's speed concerns?
In smaller maps I can see the validity because of locality of
reference, but for any decently sized map, it shouldn't matter, right?

[Russ Cox]

Right now a map[int]int uses 2 int per entry.
A map[int]*int uses 1 int + a pointer (to an int) per entry.
Go gives you the control over memory layout to
make that decision. If you want the pointer always,
write the *.

Russ

[Popog]

Using the current popular implementations, this is true, it is
however, not required for a proper implementation of Go.

I would stipulate that losing this as a feature of maps would be a
minimal loss of utility as the removal of such a feature would be all
be undetectable to Go users. The memory layout of maps is largely
unimportant to their utility. I will concede that there may be
idealistic losses if this feature were removed.

Are there any further negatives aspects to be considered?

[peterGo]

Popog,

If you would like a particular implementation of a map style type, you
can write you own package to do that.

Peter

[John Asmuth]

My point wasn't that this made it impossible. My point was that it had
nothing to do with the map type.

[Popog]

Now, to examine one advantage of changing map indexing...

TLDR, addressability of map indexing removes unneeded complexity.

I interpret Go's goal of simplicity to mean easy to learn. As such,
the syntax should serve to enhance ones understanding of the language,
or at the very least not obfuscate concepts. Go's uniformity is what
makes it much easier to learn, IMHO.

Languages like C++ have serious problems maintaining uniformity,
especially due to redundancy (#defines, typedefs, and using
declarations can all be used for type aliasing and all have different
syntaxes).

All declarations in Go can basically be read right to left to generate
the following sentence "[Declaration Type] [Identifier] is a
[Specification]" (e.g. "var i int" -> "Variable i is an int", "func
f(int) (int)" -> "Function f is a functions which takes an int and
returns an int").

This kind of simplicity is the most important feature of Go.

Now put yourself in the shoes of a young lad as he first learns how to
code. You understand programming through a lot of metaphors. Variables
are boxes, assignment is placing something into a box, pointers are
arrows that point at the box, taking the address is getting the
location of the box, dereferencing is following the arrow back to the
box, etc.

Now, attempt to process the following concept about assignment: All
LHS operands (excluding _) are addressable EXCEPT for map index
expressions. This muddles up your understanding of what assignment
means and what pointers are. Suddenly map indexing is less like a
variable and more like a function call due to the lack of
addressability of return values. But you can't assign to the return
value of a function call. This is confusing!

If map indexing are left unaddressable, it means more concepts to
comprehend and less repetition of the existing concepts. It means a
blurring of concepts and a loss of simplicity.


Please note, this post is not to say that I am confused, but that I
know a lot of first year CS students who would be.

[Cory Mainwaring]

I don't know why they'd be confused, because a first year CS student would never stumble upon it. Secondly, they would realize that:

"Ok, structs must be pointers to be played with, and maps can't give me pointers, so I either have to store the pointers in the map or I have to not use a map. Ok, so I want to use a map, lets store pointers."

And thirdly, what would really happen is:

type T struct { x int }

func A() (temp T) {

    temp = new(T) /*Error*/

    temp.x = 3

    return

}

And in the majority of cases, people would change the return type to a pointer, rather than dereference the new(). Also, temp := M[i]; temp.B(); M[i] = temp; is a much less ugly way of solving it without using a map of pointers.

So, if your problem is ugliness, you have the options of returning type *T from A() or using a temp variable intelligently in the use of B(). In the event those aren't your cup of tea, a slice or vector may come in handy for this use-case.

As for the general lack of addressability in maps, I suspect that would require that the map be contiguous, making expanding it on the fly less able and expedient.

[Popog]

On Jul 31, 10:53 am, Cory Mainwaring <olre...@gmail.com> wrote:
> I don't know why they'd be confused, because a first year CS student would
> never stumble upon it. Secondly, they would realize that:

Why would a first year CS student not stumble upon it? Should it be a
second year CS student? I learned how memory was laid out and pointers
"worked" (fun pictures!) and all that back in my second semester if I
recall correctly. It might have been third semester, but whatever.

> "Ok, structs must be pointers to be played with, and maps can't give me
> pointers, so I either have to store the pointers in the map or I have to not
> use a map. Ok, so I want to use a map, lets store pointers."

Stucts do not have to be pointers to be played with. If you wish to
modify something that is passed to a function, you must use a pointer,
that's the rule they learn.

> And thirdly, what would really happen is:
>
> type T struct { x int }
> func A() (temp T) {
>     temp = new(T) /*Error*/
>     temp.x = 3
>     return
>
> }
>
> And in the majority of cases, people would change the return type to a
> pointer, rather than dereference the new().

You don't need new, new is only if you to dynamically allocate,
(although in Go it's not the only way to). You're assuming A is a
function you can modify.

> Also, temp := M[i]; temp.B();
> M[i] = temp; is a much less ugly way of solving it without using a map of
> pointers.

It's also a huge waste of time if type T is big and B() is only a
small modification.

> So, if your problem is ugliness, you have the options of returning type *T
> from A() or using a temp variable intelligently in the use of B(). In the
> event those aren't your cup of tea, a slice or vector may come in handy for
> this use-case.

Use a slice/array in place of a map, just because maps are sucky?

> As for the general lack of addressability in maps, I suspect that would
> require that the map be contiguous, making expanding it on the fly less able
> and expedient.

I don't believe so. In fact, reading through $(GOROOT)/src/pkg/runtime/
hashmap.c, I found hash entries are composed of a "hash_hash_t" called
"hash" and a "byte[1]" called "data". Both of these are pointer types.

Hash maps appear to already be using pointers to store data no matter
what, at least in the current implementation. This would make Russ
said actually false, as a pointer is always there, regardless of
whether or not I want one. If I'm reading this right, entry data
already remains in a constant memory location when maps are resized.
So most the implementation of hashmaps would not have to be changed.

Only the way in which data is retrieved would need to be changed,
instead of memcopying the data out (which is what it currently does),
it would need to pass the pointer out to be dereferenced (which would
make it addressable). Oh, and also entries would need to be handed to
the GC, but that shouldn't be too much of a slow down, otherwise Go
wouldn't be using a GC in the first place.

[Ian Lance Taylor]

Popog <pop...@gmail.com> writes:

> I don't believe so. In fact, reading through $(GOROOT)/src/pkg/runtime/
> hashmap.c, I found hash entries are composed of a "hash_hash_t" called
> "hash" and a "byte[1]" called "data". Both of these are pointer types.

The data field is not a pointer type. The struct is allocated such that
the data array is large enough to hold the data. The code allocates
groups of elements which act as a closed hash table. When the hash
table grows, elements do indeed move around.

I agree that it is odd that map index expressions can appear on the left
hand side of an assignment but their address can not be taken (that is
also true of the blank identifier "_"). However, as others have noted,
permitting taking the address of a map index expression would be
tantamount to requiring all implementation of map[K]V to become
map[K]*V. That does not seem desirable.

Ian

[Popog]

On Aug 1, 4:06 am, Ian Lance Taylor <i...@google.com> wrote:
> The data field is not a pointer type.  The struct is allocated such that
> the data array is large enough to hold the data.  The code allocates
> groups of elements which act as a closed hash table.  When the hash
> table grows, elements do indeed move around.

My apologies for reading the source incorrectly, I should have read
more closely. I should probably not try to interpret a hash map
implementation on 4 hours of sleep.

> I agree that it is odd that map index expressions can appear on the left
> hand side of an assignment but their address can not be taken (that is
> also true of the blank identifier "_").  However, as others have noted,
> permitting taking the address of a map index expression would be
> tantamount to requiring all implementation of map[K]V to become
> map[K]*V.  That does not seem desirable.

Technically, as there is no specification for time complexity of map
operations, one could implement a map as a deque and use a linear
search to match the key. Or one could use a tree, or a hash map with
closed addressing, or a data structure no has yet thought of. I think
the main reason you find this change undesirable is because of the
implementation you have chosen to use for the moment. And I don't
think you should impose the restriction of not being addressable on
other implementations based your choice of container type. The only
requirement I'm asking is that map indexing be addressable. If that is
not a natural function of whatever container is chosen to be the
underlying type for maps, and there is no better solution, then using
a pointer is the backup solution. And every container that could
possibly support being a map will at least have that solution
available, because it has to support map[K]*V. And if someone really
needs a map with open addressing, to quote the language design FAQ,
"If a specific application can benefit from a custom implementation,
it's possible to write one but it will not be as convenient
syntactically; this seems a reasonable tradeoff".

But the reason I ask for this change still has nothing to do with the
underlying container. Whether or not this restriction is made should
be a design decision. When making this decision, there should be
thought as to whether or not it's overly difficult to implement. It's
not. There should be thought as to whether the performance will suffer
greatly. It won't. Past that point in making this decision, there
should be no further scrutinizing of the underlying structure to make.
Past that point, the only question should be, "How will this change
alter the user experience?". The answer of course, depends on the
user. For experienced users, it's a neutral change. For inexperienced
users, it's a clear benefit.

Think about this change the other way around. Pretend you decided to
use a hash map using pointers, and that map indexing was addressable.
Now pretend that someone suggested that you change the hash map
implementation so that you wouldn't be using an extra pointer, with
the caveat that map indexing would not longer be addressable. What
kind of a trade-off is that? A sucky one. What's to gain? Performance?
Screw em, if they really need performance, doing some testing and
changing the hash function and max load factor would be way more of a
performance improvement.

Or think about arrays and slices. If you could change their
implementation to some theoretical implementation that would yield
some negligible benefit, but would preclude their indexing from being
addressable, would you do it? Let's say you want the memory manager to
be able to move arrays about whenever it feels like it for compaction
purposes, which means pointers to elements would be invalidated. Is
the runtime more important than the syntax? Do changes to it override
the importance of maintaining simple, easily understandable l-values?

If Go succeeds as a language, most of the programmers are going to be
newbie coders, because most coders in the world are newbie coders and
Go's goal is to be a simple language they can understand. The majority
of these newbies will not know, and will not care, about the
underlying mechanisms of the runtime. As the creators of Go should
understand better than anyone, the way a language is truly defined is
not by what's under the hood; the interface is what's important.

Also, Ian, my apologies if I'm reading too much into it, but your
explicit reference to the blank identifier makes me think you feel
it's unaddressability justifies the incongruity of map indexing's
unaddressability. I think we can both agree the blank identifier's
lack of addressability is much more understandable and hardly
compromises either the uniformity or the simplicity of Go (although it
would be pretty neat if it were addressable, but probably a much
harder trick, and not very useful, but neat nonetheless).

[Ian Lance Taylor]

Popog <pop...@gmail.com> writes:

> I think
> the main reason you find this change undesirable is because of the
> implementation you have chosen to use for the moment.

I think it's a little deeper than that. It's because I think the
natural implementation for map is a hash table. While you're right that
Go could use a different data structure, I think the different
performance characteristics would be problematic in themselves.

Note that taking the address of a map element is interesting to consider
with regard to modifications of the map. If a is an array or slice, and
I take the address of a[5], and then I change a[5], it's clear that the
value I see through the pointer should change similarly. It's also
clear that that should be true if I change a[6] and then change a[5].
In fact, the value will always be consistent unless I change a itself.

Presumably, if you could take the address of a map element, we would
want to the same rules to apply. If I take the address of m["a"], then
changing m["b"] should not affect that, even if "b" were not previously
in the map. If you extend that to large numbers of insertions, I wonder
whether you can really come up with a data structure which supports that
without making m["a"] be a pointer.

> But the reason I ask for this change still has nothing to do with the
> underlying container. Whether or not this restriction is made should
> be a design decision. When making this decision, there should be
> thought as to whether or not it's overly difficult to implement. It's
> not. There should be thought as to whether the performance will suffer
> greatly. It won't. Past that point in making this decision, there
> should be no further scrutinizing of the underlying structure to make.

I think you've correctly identified the tradeoffs. However, I don't
think I'm with you in concluding that the performance issue is
negligible. Making every map insertion requires allocating a new memory
object is definitely a performance cost. Is it worth paying the cost to
get a bit more orthogonality in the language? Perhaps. But for me it's
not an obvious decision.

> Or think about arrays and slices. If you could change their
> implementation to some theoretical implementation that would yield
> some negligible benefit, but would preclude their indexing from being
> addressable, would you do it?

I would consider it, yes.

Ian

[David Roundy]

On Sun, Aug 1, 2010 at 11:10 AM, Ian Lance Taylor <ia...@google.com> wrote:
> I think you've correctly identified the tradeoffs.  However, I don't
> think I'm with you in concluding that the performance issue is
> negligible.  Making every map insertion requires allocating a new memory
> object is definitely a performance cost.  Is it worth paying the cost to
> get a bit more orthogonality in the language?  Perhaps.  But for me it's
> not an obvious decision.

I agree, but would also want to emphasize that raw memory use is an
important consideration as well. Storing an extra pointer for each
element seems liable to dramatically increase the total size of a map
(e.g. for map[int]int with 64 bit pointers and 32 bit ints), which is
a serious issue. True, it's hard to predict just how big this
increase will be, but I'd prefer that the language not make a choice
that precludes the use of more efficient data structures. For
instance, I could imagine clever data structures for map[uint8]bool
that could involve storing the bools as bit fields. I wouldn't
implement that optimization now, but it seems like not a bad idea to
allow for future optimizations in the implementation.

David

[Popog]

On Aug 1, 8:10 am, Ian Lance Taylor <i...@google.com> wrote:
> Presumably, if you could take the address of a map element, we would
> want to the same rules to apply.  If I take the address of m["a"], then
> changing m["b"] should not affect that, even if "b" were not previously
> in the map.  If you extend that to large numbers of insertions, I wonder
> whether you can really come up with a data structure which supports that
> without making m["a"] be a pointer.

I believe it will be difficult to come up with an alternate solution
which retains the performance characteristics, but I've never invented
a truly new data structure that served a generalized purpose.

> I think you've correctly identified the tradeoffs.  However, I don't
> think I'm with you in concluding that the performance issue is
> negligible.  Making every map insertion requires allocating a new memory
> object is definitely a performance cost.  Is it worth paying the cost to
> get a bit more orthogonality in the language?  Perhaps.  But for me it's
> not an obvious decision.

This cost can be amortized, along with the loss of locality of
reference, by using memory management techniques such as chunking. You
could even further amortize the cost by doing background allocations
of those chunks. The true cost can't be known until it's implemented
and tested. If Go can remain a competitively fast language with the
inclusion of garbage collection, it can remain a competitively fast
language with the inclusion of a slightly slower map type.

> I would consider it, yes.

Well, I suppose I'm glad that you would consider it. You seem to be a
very considerate person, and without that I suppose you wouldn't even
be considering my crazy suggestions. So, I appreciate your
consideration, even though I may disagree with your prioritization.

On Aug 1, 2:39 pm, David Roundy <roun...@physics.oregonstate.edu>
wrote:

> I agree, but would also want to emphasize that raw memory use is an
> important consideration as well. Storing an extra pointer for each
> element seems liable to dramatically increase the total size of a map
> (e.g. for map[int]int with 64 bit pointers and 32 bit ints), which is
> a serious issue. True, it's hard to predict just how big this
> increase will be, but I'd prefer that the language not make a choice
> that precludes the use of more efficient data structures. For
> instance, I could imagine clever data structures for map[uint8]bool
> that could involve storing the bools as bit fields. I wouldn't
> implement that optimization now, but it seems like not a bad idea to
> allow for future optimizations in the implementation.

Here's the thing, all those memory and performance issues can be
solved by using a specialized hashmap packages (or got files) for
advanced users who want to rely on a specific implementation,
regardless of what implementation of Go they're using. The issue of
having a homogeneous syntax cannot be dealt with in such a way.