LWN: Comments on "The XArray data structure"

The XArray data structure

dafnaf — Tue, 23 Jul 2024 12:58:17 +0000

>> The XArray is intended to have performance and usage characteristics as close as possible to a C native array. Unlike, say, a hash table.

could you clarify that? since afaik a hash table also suppose to have the same complaxity as an array, that is avarage of O(1) for get/set as the linked list in each bucket suppose to be "short enough". So when should we use hash table and when xarray?

(XArray) C++ → C naming conversions

nybble41 — Sun, 31 Mar 2019 16:22:21 +0000

> How would "std::map<unsigned long, std::tuple<void*, bool[3]>>, Alloc> …" even map to C as a name?

This is a solved problem. After all, G++ already generates C-compatible names which encode their C++ argument types.

Just call it St3mapImSt5tupleIJPvA3_bEESt4lessImESaISt4pairIKmS3_EEE_array. :-)

(XArray) C++ → C naming conversions

zenaan — Sun, 31 Mar 2019 00:49:06 +0000

>> (That said, it's totally a std::map<unsigned long, std::tuple<void*, bool[3]>>, Alloc> with internal locking, stable iterators, and atomic value operators...except for the parts where it's different from that)

> I'm not a C++ programmer, nor a theoretician. I'm happy for the API to not match C++, as long as it matches people's expectations.

How would "std::map<unsigned long, std::tuple<void*, bool[3]>>, Alloc> with internal locking, stable iterators, and atomic value operators..." even map to C as a name?

Discluding the behaviour characteristics, and taking the first letter of each C++ 'word' → smulstvbA_array perhaps?

The XArray data structure

andresfreund — Fri, 02 Feb 2018 11:07:37 +0000

Sorry to be that blunt: Could you perhaps consider commenting a little less frequently? You comment on nearly everything - not infrequently the majority of new comments are yours. Even ignoring them reduces the usability of the "unread comments" page noticeably.

The XArray data structure

Wol — Fri, 02 Feb 2018 09:25:34 +0000

No. The USERS don't give a monkeys. The implementers care deeply ...

Cheers,
Wol

The XArray data structure

Wol — Fri, 02 Feb 2018 09:24:49 +0000

That's a sparse array ... :-)

Cheers,
Wol

The XArray data structure

nix — Mon, 29 Jan 2018 13:50:51 +0000

That's exactly what I was thinking. This is not a tree. It's an array that happens to have a tree as its internal storage representation currently. You can't have an array element with no value! (Sure, it's sparse, but all that means is that null elements are cheaper than non-null ones).

The XArray data structure

willy — Mon, 29 Jan 2018 09:54:13 +0000

You'd be amazed how few places actually need the preloading functionality. We had 42 calls to various forms of the preload functions.

I've entirely removed the radix tree preload from my tree and I have only seven calls to xa_reserve() (in four files). Until a few weeks ago, I hadn't found anywhere with sufficiently complex locking requirements to need xa_reserve(). The general pattern that needs xa_reserve() is:

radix_tree_preload();
spin_lock(some_other_lock);
spin_lock(tree_lock);
radix_tree_insert();
...

Sometimes you can invert the order of the locks, or combine the two locks, or resort to the advanced API in order to explicitly handle unlocking before allocating memory, but converting it to:

xa_reserve();
spin_lock(other_lock);
xa_store();

is easier.

If the out-of-tree lustre code has developed new and exciting ways to use the radix tree API, then they'll get to fix it up ... maintaining out of tree patches is expensive and drivers/staging/ is there to lower the cost.

The XArray data structure

willy — Mon, 29 Jan 2018 08:58:31 +0000

Hi Zygo, great to hear from you again

The XArray is intended to have performance and usage characteristics as close as possible to a C native array. Unlike, say, a hash table. I don't want anyone to be surprised by a mismatch between the naming and the behaviour.

You're right that there's no right name for this data structure. The closest thing I've found in the literature is the Judy Array. So I sidestepped the question of what the _data structure_ is called and focused on what it provides (an array abstraction). That enables us to change the underlying implementation as we see fit. There were a number of ways the old API leaked the internal details of the data structure to the callers, and I've eliminated those.

I'm not a C++ programmer, nor a theoretician. I'm happy for the API to not match C++, as long as it matches people's expectations.

The XArray data structure

willy — Mon, 29 Jan 2018 04:27:46 +0000

Thanks for writing up my talk, Jon!

I have a quibble with your article,

> The return value on success is the previous value (if any) that was stored at index.

This is the kind of radix tree thinking that I'm trying to eradicate. Every index has a value stored at it. An "empty array" has a NULL pointer stored at every index; and a freshly-initialised array is empty. Just deleting the parenthetical would make me happy :-)

If you can suggest an improvement to the documentation that would help people get to this mindset, I'd be more than happy to incorporate it. It may just be a matter of time and people getting used to the new way of thinking.

The XArray data structure

ncultra — Fri, 26 Jan 2018 22:09:28 +0000

The api is similar to the existing, though sparsely used, flex_array library, which has pre-allocation but not locking. I have found it useful but am concerned that no upstream kernel code seems to be using flex_arrays.

The XArray data structure

zblaxell — Thu, 25 Jan 2018 21:27:55 +0000

Everyone working in a new programming environment, even if the language is familiar, has to figure out whether each thing with the word "array" in its name is some flavor of btree, dict, hash table, map, rbtree, set, vector, constant pointer + index * size, "other", or "not implemented here." Once that's known for "array", one then has to learn the local names for all the other things too. They all have different capabilities, limitations, performance, and unimaginable quirks that make the wrong choice wrong for at least one situation.

The wrong word was used here, but that was inevitable, as there's always someone who joins the party late and complains "but in my tribe we always called that by another name." There could never have been a correct name for this structure--only a previously unused one, preferably something with a short unique acronym to use as a prefix.

(That said, it's totally a std::map<unsigned long, std::tuple<void*, bool[3]>>, Alloc> with internal locking, stable iterators, and atomic value operators...except for the parts where it's different from that)

The XArray data structure

rweikusat2 — Thu, 25 Jan 2018 20:19:08 +0000

> Yes, but I think "a map structure keyed by an integer" is essentially the definition of "array" (at least as an abstract data type), and
> it's generally easier to use the shorter name.

Abstractly, an 'array' is an ordered set of values which can be accessed by position in constant time. That's something entirely different from a map associating members from a set of keys with members from a set of values. Eg, they key set of a map using integer keys might be {-60, -1, 1434, 131072}.

The XArray data structure

bof — Thu, 25 Jan 2018 18:00:43 +0000

> (Except in Javascript, where an array is actually a map structure keyed by the decimal string representation of an integer.)

Or in PHP, where it can be both, at the same time...

> The concrete implementation of that data type is a separate issue; it could be a series of consecutive memory addresses, or a hash table, or a red-black tree, or a radix tree, or something that changes depending on the density of its contents, etc. But users of an API shouldn't care about those implementation details - they just care that it behaves like an abstract array with certain performance characteristics, so it seems sensible to call it an array.

In kernel space, users probably do care about such details very much. Otherwise the kernel would have been rewritten in PHP a long time ago...

The XArray data structure

excors — Thu, 25 Jan 2018 17:20:22 +0000

Yes, but I think "a map structure keyed by an integer" is essentially the definition of "array" (at least as an abstract data type), and it's generally easier to use the shorter name.

(Except in Javascript, where an array is actually a map structure keyed by the decimal string representation of an integer.)

The concrete implementation of that data type is a separate issue; it could be a series of consecutive memory addresses, or a hash table, or a red-black tree, or a radix tree, or something that changes depending on the density of its contents, etc. But users of an API shouldn't care about those implementation details - they just care that it behaves like an abstract array with certain performance characteristics, so it seems sensible to call it an array.

The XArray data structure

skitching — Thu, 25 Jan 2018 14:42:48 +0000

Isn't this equivalent to a map (aka dictionary) structure keyed by an integer? That metaphore works better for me than a "dynamic array".

The XArray data structure

LawnGnome — Wed, 24 Jan 2018 21:20:04 +0000

Apparently there have been issues with video recording lockups at past conferences not being noticed until a talk has already been underway, so there needs to be movement in the frame for a quick sanity check as the speaker is preparing to begin. Some conference venues have clocks, but the linux.conf.au venue doesn't this year, so they've deployed a small clowder of maneki-neko instead.

Preallocation

corbet — Wed, 24 Jan 2018 21:16:39 +0000

Indeed, preallocation is not entirely removed. It's not visible in the normal API, though, and has become something that most callers need not worry about.

The XArray data structure

meyert — Wed, 24 Jan 2018 20:48:17 +0000

What is the reason for the maneki-nekos at conferences these days?

The XArray data structure

Paf — Wed, 24 Jan 2018 13:54:49 +0000

Yeah, the Lustre filesystem (possibly not in the upstream kernel version) has a tricky interaction with a radix tree where it has to do a preload or it can deadlock. I didn’t see how it was possible to not have the preload in some form. Relieved to hear it’s still there.

The XArray data structure

cborni — Wed, 24 Jan 2018 12:37:49 +0000

The preloading is used in some cases with tricky locking. Looking at the patches, preloading is not removed, it is now replace by a different scheme with a call names xa_reserve.