# Inserting string keys in arrays at any position

- Thread: https://externals.io/message/101041
- Original archive: https://news-web.php.net/php.internals/101041
- Started by Thomas Hruska on 2017-11-03T13:51:48+00:00
- Messages: 3
- Reply by email to internals@lists.php.net
- More for agents: search with https://externals.io/search.md?q={query} · JSON API at https://externals.io/api · documentation at https://externals.io/llms.txt

---

## #101041 — Thomas Hruska — 2017-11-03T13:51:48+00:00

URL: https://externals.io/message/101041#101041

I've been wondering for some time why PHP does not have the ability to 
efficiently insert string keys before/after an existing string key.

Let's say I have an array of 10,000 string key/value pairs and I want to 
insert five new string key/value pairs at specific positions in the 
existing array.  Unless I've missed something, despite looking at each 
of the array_...() functions, this is not possible in userland without 
copying the entire array to insert the new elements (or some real 
hackery such as append with some tracking info and use a function like 
 `uksort()` to somehow only move the newly added items).  There are several 
userland functions in the PHP documentation comments and also on 
StackOverflow that end up recreating the array each time they are 
called.  Several examples:

https://stackoverflow.com/a/7257599/917198

http://us1.php.net/manual/en/function.array-splice.php


As the author of the OrderedHash implementation here:

https://github.com/cubiclesoft/cross-platform-cpp

I provide an ordered hash data structure that is similar-ish to the PHP 
array implementation, but it also has support for inserting a node 
anywhere in the OrderedHash by making a few pointer adjustments. 
Shifting a few pointers around is usually magnitudes faster than 
performing memory allocations and copying data.

-- 
Thomas Hruska
CubicleSoft President

I've got great, time saving software that you will find useful.

http://cubiclesoft.com/

And once you find my software useful:

http://cubiclesoft.com/donate/

---

## #101042 — Bishop Bettini — 2017-11-03T14:46:33+00:00

URL: https://externals.io/message/101041#101042 · In reply to: #101041

On Fri, Nov 3, 2017 at 9:51 AM, Thomas Hruska <thruska@cubiclesoft.com>
wrote:

> I've been wondering for some time why PHP does not have the ability to
> efficiently insert string keys before/after an existing string key.
>
> Let's say I have an array of 10,000 string key/value pairs and I want to
> insert five new string key/value pairs at specific positions in the
> existing array.  Unless I've missed something, despite looking at each of
> the array_...() functions, this is not possible in userland without copying
> the entire array to insert the new elements


It's impossible in user-land because, well, that's just how HashTable works
under the hood. Quoting nikic [1]:

> The arData array stores the elements in order of insertion. So the first
array element will be stored in arData[0], the second in arData[1] etc.
This does not in any way depend on the used key, only the order of
insertion matters here.

That last part is important: the keys from user-land have no bearing on the
order in memory. If one wants to effect the in-memory ordering, one must
create a new user-land array and insert them in the desired order.


As the author of the OrderedHash implementation here:
>
> https://github.com/cubiclesoft/cross-platform-cpp
>
> I provide an ordered hash data structure that is similar-ish to the PHP
> array implementation, but it also has support for inserting a node anywhere
> in the OrderedHash by making a few pointer adjustments. Shifting a few
> pointers around is usually magnitudes faster than performing memory
> allocations and copying data.


Shifting elements in a HashTable.arData would not be cheap. But, honestly I
can't think of a scenario where changing the in-memory order would be
necessary. If I want an array that traverses in order, I'll insert in
order. Otherwise, I'll sort on demand. What seems to matter most is
efficiency of lookup by key.


> --
> Thomas Hruska
> CubicleSoft President
>

bishop

[1]:
http://nikic.github.io/2014/12/22/PHPs-new-hashtable-implementation.html

---

## #101111 — Thomas Hruska — 2017-11-08T19:17:34+00:00

URL: https://externals.io/message/101041#101111 · In reply to: #101042

> On Fri, Nov 3, 2017 at 9:51 AM, Thomas Hruska <thruska@cubiclesoft.com>
> wrote:
> 
> http://nikic.github.io/2014/12/22/PHPs-new-hashtable-implementation.html

Ah.  Very clever and cool.  That memory layout does indeed pose a 
problem with random order insertions of string keys.  Detachable nodes 
are more useful to me in C++ for a general-purpose data structure but I 
can see the benefits of doing this for PHP 7, which takes advantage of 
the most common array usage patterns (i.e. an array).

After reading that post, I was inspired to implement PackedOrderedHash:

https://github.com/cubiclesoft/cross-platform-cpp

I can definitely see why PHP 7 adopted the structure.  My own benchmarks 
of PackedOrderedHash show significant performance improvements.

You'll note that in PackedOrderedHash I excluded inserting just anywhere 
- likely for the same reason that PHP doesn't offer such a feature.  I 
still think PHP could natively offer string key-based insertions even 
though it'll require moving elements of an array around.  That's likely 
to be faster than rebuilding the whole array.

Thanks for the long writeup and Nikic for the blog post.

-- 
Thomas Hruska
CubicleSoft President

I've got great, time saving software that you will find useful.

http://cubiclesoft.com/

And once you find my software useful:

http://cubiclesoft.com/donate/