Address of map entries

[Robert Johnstone]

Hello,

To avoid unnecessary allocations, I was evaluating a modification in a program where we would embed the structure directly in the map.  i.e. replace map[string]*Foo with map[string]Foo.  Since the structure is mutable, I want to have access to a *Foo, but the following is an error:

     v, ok := &mymap["a"]

You cannot take the address of map entries.  Also, you cannot call pointer methods on map entries.

Since you can update a copy of the struct, and then assign that back to the map, there is an easy work around for this limitation.  However, I'm still interested to know why the limitation exists.  Could the language be modified to allow these operations?

Robert

[Vanja Pejovic]

I'm not sure about the implementation of maps (except that it's a hash map), but I can imagine it's because map entries do not have a constant address. Supposed you put an item in a map. Its address is wherever it is positioned then. You store that address somewhere in your own code. Now insert a bunch of items into the map, causing a rehash. Your original item will be moved and its address will be different.

Robert

--
 
 

[Volker Dobler]

Hi,

> To avoid unnecessary allocations, I was evaluating a modification in a
> program where we would embed the structure directly in the map.  i.e.
> replace map[string]*Foo with map[string]Foo.

How would this help avoiding allocations?

It might be easier if you implement your own allocator
and stick to pointers in the map.

I actually do not know why you cannot take the address
of a map entry, but i suppose this is because the address
might change due to reorganisation of the map during
its lifetime with the result of a dangling pointer.

Volker

[John Beshir]

The map is allowed to internally copy and move around values. This
would invalidate pointers into the map, so it isn't legal to get the
pointer of something stored in the map.

[Robert Johnstone]

When you store a pointer in the map, you have to separately allocate memory for the structure itself.  Since Go will automatically allocate memory on the heap for structures when you take the address (barring certain exception regarding escape analysis), there is an additional allocation for &Foo{} compared to Foo{}.  To summarize, &Foo{} likely lives on the heap, Foo{} will be on the stack.  Similarly, &Foo{} will live in a separate section of the heap from the map entry, while Foo{} will live inside the map entry.

Memory allocation is an area in Go where a lot happens implicitly behind the scene.

[Robert Johnstone]

That is surprising, but certainly explains the restriction.  Thank-you.

[Kyle Lemons]

On Thu, Oct 4, 2012 at 9:20 AM, Robert Johnstone <r.w.jo...@gmail.com> wrote:

That is surprising, but certainly explains the restriction.  Thank-you.

Is it?  That's also why you have to lock a map if you're accessing it concurrently.  Pretty much every map implementation I've seen resizes itself when it gets overfull.

 

On Thursday, 4 October 2012 10:46:43 UTC-4, John Beshir wrote:

The map is allowed to internally copy and move around values. This
would invalidate pointers into the map, so it isn't legal to get the
pointer of something stored in the map.

--
 
 

[Robert Johnstone]

If the map was implemented using an RB-tree, the location of entries would be stable.  If it was implemented using a hash with linked lists for overflow, the location of entries would be stable.  I had run a short list of implementations in my head, and none of them indicates that the entries themselves would be moved.  Obviously, I did not include the right implementation, so I was surprised.

P.S. All of the above would require a lock as well to be accessed concurrently, so that is hardly an indicator either way.

[Jan Mercl]

On Fri, Oct 5, 2012 at 3:23 PM, Robert Johnstone
<r.w.jo...@gmail.com> wrote:
> If the map was implemented using an RB-tree, the location of entries would
> be stable. If it was implemented using a hash with linked lists for
> overflow, the location of entries would be stable. I had run a short list
> of implementations in my head, and none of them indicates that the entries
> themselves would be moved. Obviously, I did not include the right
> implementation, so I was surprised.

Check e.g. http://en.wikipedia.org/wiki/Hash_table#Dynamic_resizing

-j

[Rob Pike]

Use an arena allocator for the structs you create, and a free list if
you free them. That will amortize the allocation overhead.

-rob

[Rémy Oudompheng]

On 2012/10/5 Robert Johnstone <r.w.jo...@gmail.com> wrote:
> If the map was implemented using an RB-tree, the location of entries would
> be stable. If it was implemented using a hash with linked lists for
> overflow, the location of entries would be stable. I had run a short list
> of implementations in my head, and none of them indicates that the entries
> themselves would be moved. Obviously, I did not include the right
> implementation, so I was surprised.

How do you do that without doing a memory allocation for each element
of the map?

Rémy.