www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - RE: Are Gigantic Associative Arrays Now Possible?

reply dlangPupil <x x989898998.com> writes:
Hello to all!  As a (D, and coding and forum) newbie I'm learning 
about D's associative arrays (AAs), and their tiny latency 
regardless of AA size. Cool!

One practical limitation on the practical maximum AA size is 
memory/disk paging.  But maybe this limit could be overcome with 
the latest SSDs, whose nonvolatile memory can be addressed like 
RAM.

The article below says that Intel Optane SSDs:
	-allow reads and writes can on individual bytes.
	-have a latency 10x of DRAM (but  AAs' latency is so low that 
this might not matter in many cases).
	-currently offer 375GB of "RAM" for $1,500.
	-will support up to 3 TB on 2 socket Xeon systems (48TB on 
4-socket).
	-will be supplemented with Optane DIMMs in the future.

Some questions that arise are...

1) Wouldn't using such "RAM" eliminate any paging issue for 
super-gigantic AAs?
2) What other bottlenecks could arise for gigantic AAs, e.g., 
garbage collection?
3) Would an append-only data design mitigate GC or other 
bottlenecks?
4) Has anyone tried this out?

What a coup if D could "be the first" lang to make this 
practical.  Thanks.

https://arstechnica.com/information-technology/2017/03/intels-first-optane-ssd-375gb-that-you-can-also-use-as-ram/
Mar 22
next sibling parent Laeeth Isharc <laeethnospam nospam.laeeth.com> writes:
On Wednesday, 22 March 2017 at 20:00:56 UTC, dlangPupil wrote:
 Hello to all!  As a (D, and coding and forum) newbie I'm 
 learning about D's associative arrays (AAs), and their tiny 
 latency regardless of AA size. Cool!

 One practical limitation on the practical maximum AA size is 
 memory/disk paging.  But maybe this limit could be overcome 
 with the latest SSDs, whose nonvolatile memory can be addressed 
 like RAM.

 The article below says that Intel Optane SSDs:
 	-allow reads and writes can on individual bytes.
 	-have a latency 10x of DRAM (but  AAs' latency is so low that 
 this might not matter in many cases).
 	-currently offer 375GB of "RAM" for $1,500.
 	-will support up to 3 TB on 2 socket Xeon systems (48TB on 
 4-socket).
 	-will be supplemented with Optane DIMMs in the future.

 Some questions that arise are...

 1) Wouldn't using such "RAM" eliminate any paging issue for 
 super-gigantic AAs?
 2) What other bottlenecks could arise for gigantic AAs, e.g., 
 garbage collection?
 3) Would an append-only data design mitigate GC or other 
 bottlenecks?
 4) Has anyone tried this out?

 What a coup if D could "be the first" lang to make this 
 practical.  Thanks.

 https://arstechnica.com/information-technology/2017/03/intels-first-optane-ssd-375gb-that-you-can-also-use-as-ram/
Hi. I am very interested in this topic, although I don't really have answers for your questions. See the acm article which I mentioned last year I think on forum. https://queue.acm.org/detail.cfm?id=2874238 "For the entire careers of most practicing computer scientists, a fundamental observation has consistently held true: CPUs are significantly more performant and more expensive than I/O devices. The fact that CPUs can process data at extremely high rates, while simultaneously servicing multiple I/O devices, has had a sweeping impact on the design of both hardware and software for systems of all sizes, for pretty much as long as we've been building them. This assumption, however, is in the process of being completely invalidated. The arrival of high-speed, non-volatile storage devices, typically referred to as Storage Class Memories (SCM), is likely the most significant architectural change that datacenter and software designers will face in the foreseeable future. SCMs are increasingly part of server systems, and they constitute a massive change: the cost of an SCM, at $3-5k, easily exceeds that of a many-core CPU ($1-2k), and the performance of an SCM (hundreds of thousands of I/O operations per second) is such that one or more entire many-core CPUs are required to saturate it. This change has profound effects: 1. The age-old assumption that I/O is slow and computation is fast is no longer true: this invalidates decades of design decisions that are deeply embedded in today's systems. 2. The relative performance of layers in systems has changed by a factor of a thousand times over a very short time: this requires rapid adaptation throughout the systems software stack. 3. Piles of existing enterprise datacenter infrastructure—hardware and software—are about to become useless (or, at least, very inefficient): SCMs require rethinking the compute/storage balance and architecture from the ground up. " It's a massive relative price shock - storage vs CPU - and whole structures around it will need to be utterly transformed. Intel say it's the biggest technological breakthrough since the internet. I'm good at recognising moments of exhaustion in old trends and the beginning of new ones, and I've thought for some time now that people were complacently squandering CPU performance just as conditions were tending to favour it becoming important again. https://www.quora.com/Why-is-Python-so-popular-despite-being-so-slow/answer/Laeeth-Isharc?srid=35gE I don't know how data structures and file systems should adapt to this. But I do think the prospective return on efficient code just went up a lot - as far as I can see, this shift is very good for D.
Mar 23
prev sibling next sibling parent reply Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Wednesday, 22 March 2017 at 20:00:56 UTC, dlangPupil wrote:
 1) Wouldn't using such "RAM" eliminate any paging issue for 
 super-gigantic AAs?
 2) What other bottlenecks could arise for gigantic AAs, e.g., 
 garbage collection?
Increasing the size of a hash table would be prohibitively expensive. You need a data-structure that can grow gracefully.
 What a coup if D could "be the first" lang to make this 
 practical.  Thanks.
This is more an OS issue than a language issue. Although it could boost high-level numeric-oriented languages and functional languages that cache expensive computations. Low level languages are pretty much in the same boat.
Mar 23
parent reply dlangPupil <x x989898998.com> writes:
On Thursday, 23 March 2017 at 10:27:36 UTC, Ola Fosheim Grøstad 
wrote:
 Increasing the size of a hash table would be prohibitively 
 expensive. You need a data-structure that can grow gracefully.
Hi Ola, Are the hash tables you refer to the ones that D uses in the background to implement associative arrays, or the ones that a programmer might create using AAs? --If the former, then perhaps the AA's hash function could be tweaked for terabyte-range SSD "RAM". But even if the typical 2:1 bucket/data storage ratio couldn't be improved, then creating 32 TB of buckets would still allow 16 TB of nearly-instantly-addressable data (on a 4-core Xeon w/ 48 TB Optane SSD). --If the latter, then my goal is design something that makes specific items randomly and instantly accessible, like a hash table, but with zero potential collisions. Thanks!
Mar 23
parent reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Fri, Mar 24, 2017 at 12:27:00AM +0000, dlangPupil via Digitalmars-d wrote:
 On Thursday, 23 March 2017 at 10:27:36 UTC, Ola Fosheim Grstad wrote:
 
 Increasing the size of a hash table would be prohibitively
 expensive.  You need a data-structure that can grow gracefully.
Hi Ola, Are the hash tables you refer to the ones that D uses in the background to implement associative arrays, or the ones that a programmer might create using AAs? --If the former, then perhaps the AA's hash function could be tweaked for terabyte-range SSD "RAM". But even if the typical 2:1 bucket/data storage ratio couldn't be improved, then creating 32 TB of buckets would still allow 16 TB of nearly-instantly-addressable data (on a 4-core Xeon w/ 48 TB Optane SSD). --If the latter, then my goal is design something that makes specific items randomly and instantly accessible, like a hash table, but with zero potential collisions. Thanks!
How do SSD access speeds compare with L1 and L2 cache speeds? You have to keep in mind that one downside of hashtables is that they tend to be unfriendly towards caching hierarchies, because generally the hash function is designed to scatter hash keys as widely and as randomly as possible (to minimize collisions), meaning that potentially *every* hash lookup will be a cache miss, perhaps more, depending on how collision resolution is handled, which can be a big performance killer. For certain applications, where key lookups are more-or-less random, this is the best you could do, but for a good number of applications, there tends to be some correlation between lookups, and even things like B-trees could potentially do better because of their cache-friendliness (and locality), even if you assume I/O is much faster than your traditional spindle-based hard drive. The O(log n) could have a much smaller constant than the hashtable O(1) if lookups tend to be correlated (i.e., exhibit locality), and lots more cache misses are incurred in the latter. Having said that, though, large-capacity low-latency SSDs are very interesting to me because I'm interested in certain applications that involve very large lookup tables. Currently I'm just using traditional hashtables, but once you get to a certain size, I/O overhead dominates and progress grinds to a halt. I've been researching ways of taking advantage of locality to ease this, but so far haven't gotten it to actually work yet. T -- People say I'm indecisive, but I'm not sure about that. -- YHL, CONLANG
Mar 23
parent reply dlangPupil <x x989898998.com> writes:
On Friday, 24 March 2017 at 06:30:25 UTC, H. S. Teoh wrote:

 You have to keep in mind that one downside of hashtables is 
 that they tend to be unfriendly towards caching hierarchies
...
 For certain applications, where key lookups are more-or-less 
 random, this is the best you could do, but for a good number of 
 applications, there tends to be some correlation between 
 lookups, and even things like B-trees could potentially do 
 better because of their cache-friendliness (and locality), even 
 if you assume I/O is much faster than your traditional 
 spindle-based hard drive. The O(log n) could have a much 
 smaller constant than the hashtable O(1) if lookups tend to be 
 correlated (i.e., exhibit locality), and lots more cache misses 
 are incurred in the latter.

 Having said that, though, large-capacity low-latency SSDs are 
 very interesting to me because I'm interested in certain 
 applications that involve very large lookup tables.  Currently 
 I'm just using traditional hashtables, but once you get to a 
 certain size, I/O overhead dominates and progress grinds to a 
 halt.  I've been researching ways of taking advantage of 
 locality to ease this, but so far haven't gotten it to actually 
 work yet.


 T
Thanks T for the great insight. Very helpful! Nice to see that you, Laeeth, the ACM, Intel and Micron all agree: this new technology could be very disruptive. In addition to prevalence of random lookups, certain additional app conditions and designs might make "gigantic AAs" more useful or competitive with alternatives: 1. Use by programmers who need a data structure that's easier to reason about or faster and safer to implement or prototype, and easier for future users to read and maintain. 2. Apps with large tables that use (or could use) non-natural keys, e.g., crypto-quality GUIDs, which can't benefit from (or impose the extra computational cost of) the sorting that must be performed and maintained on natural key values (e.g., LastName="Smith") in order to use a B-Tree search. 3. Tables (and related tables) whose row data (and even aggregate data) could be "clumped" (think "documentized") to achieve a singularity (and not merely some degree of locality), thus consolidating multiple lookups into a single lookup. -In other words, a key's value is itself an array of data that can be fetched in a single lookup. -The key id for each "next" (updated) version of a document could also be stored with the current version. -The next key-value entry to hold the update could be created immediately but not have its values written unless and until the prior version of the document has changed. -Better yet in an append-only design, creation of the next key-value entry could be deferred until a revision actually occurs. -Such "chained documentization" would automate histories, and could be further abstracted and adapted (e.g., with columnstore concepts) to accommodate apps in which lookups aren't mostly random. Finally, re: caches: I haven't found whether it is or isn't possible to combine a server's DRAM and its Optane SSD RAM or DIMMs to form a single pool of RAM. Mixing DIMMS of different speeds is a no-no; but if this could be done, then the hottest data could be "cached" in DRAM and thus spared the 10x latency penalty of the SSD device.
Mar 24
parent reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Fri, Mar 24, 2017 at 04:59:00PM +0000, dlangPupil via Digitalmars-d wrote:
[...]
 In addition to prevalence of random lookups, certain additional app
 conditions and designs might make "gigantic AAs" more useful or
 competitive with alternatives:
 
 1.  Use by programmers who need a data structure that's easier to
 reason about or faster and safer to implement or prototype, and easier
 for future users to read and maintain.
This point is arguable, since a B tree is pretty well-known and thus not difficult to reason about. Generally, whether you use a hashtable of a B tree or something else, the high-level view is that it's some opaque data structure that, given some key K, returns some value V. Which underlying algorithm is used is an implementation detail. And generally as far as application programmers are concerned, you wouldn't want to implement an advanced data structure from scratch; you'd use an off-the-shelf library that has already implemented it.
 2.  Apps with large tables that use (or could use) non-natural keys,
 e.g., crypto-quality GUIDs, which can't benefit from (or impose the
 extra computational cost of) the sorting that must be performed and
 maintained on natural key values (e.g., LastName="Smith") in order to
 use a B-Tree search.
Encrypted GUIDs is a very good point. You probably can't expect much locality from that. But this point, and the following, presume a rather specific use case, i.e., document retrieval, presumably over the network. The application of hashtables and B-trees, however, is far wider in scope. In particular, what I had in mind when I asked about cache speeds is compute-intensive (as opposed to I/O intensive) processes. These two domains of application are quite different in some ways. In document retrieval, for example, if you view it as a server serving documents over the network to a set of clients, having 1 I/O roundtrip per lookup is probably acceptable, because the time it takes to send the document over the network to the client is large enough that making lookups any faster probably won't make too much of a difference. Besides, if client requests are essentially unpredictable, then 1 I/O roundtrip is about the best you could do. In CPU-intensive computations, however, the cache hierarchy becomes very prominent, because you're talking about CPU speeds vs. RAM speeds, which is currently a rather large gap. Being cache-friendly could mean a difference on the scale of orders of magnitude in terms of overall performance. If you're talking about data lookups inside a compute-intensive inner loop, having 1 I/O roundtrip per iteration is unacceptable. Even 1 L1 cache miss per iteration may be unacceptable, depending on the application. Ideally, you want to maximize the number of iterations per L1 cache miss, and then on the next level, squeeze as many L1 misses onto L2 as possible before you have to go to L3 or revert to RAM, because RAM is slow, relatively speaking, even if it's still very fast compared to an I/O roundtrip to the hard disk. In other words, you want as much locality as you can possibly get in your memory accesses -- the entire cache hierarchy, after all, is built on the premise of memory accesses exhibiting locality. Furthermore, when it comes to CPU-intensive applications, quite often you already know the pattern of lookups beforehand, since it's usually coming from within the application itself, not from external clients that may be completely unpredictable. So you can usually predict the next n memory accesses much more easily, and take advantage of it by organizing your data structure around that. [...]
 Finally, re: caches: I haven't found whether it is or isn't possible
 to combine a server's DRAM and its Optane SSD RAM or DIMMs to form a
 single pool of RAM.  Mixing DIMMS of different speeds is a no-no; but
 if this could be done, then the hottest data could be "cached" in DRAM
 and thus spared the 10x latency penalty of the SSD device.
If the SSD device incurs a 10x latency penalty, that's still a far cry from L1/L2 cache latencies! True, it will help in the worst case when you have no choice but to take an I/O roundtrip (a hard drive would be far slower)... but this would hardly be anything revolutionary if DRAM is still faster. At the end of the day, you're still talking about a memory hierarchy with L1/L2 at the top, L3 and RAM in between, and hard drive / SSD at the bottom. If so, then the cache-unfriendliness of hashtables still applies, and we still have to work with finding ways of improving hashtable locality, e.g., with locality-sensitive hashing, cache-oblivious hashtables, etc., or use a more cache-friendly data structure like B-trees or one of the newer cache-oblivious trees. (In my case, though, B-trees may not represent much of an improvement, because I'm dealing with high-dimensional data that cannot be easily linearized to take maximum advantage of B-tree locality. So at some level I still need some kind of hash-like structure to work with my data. But it will probably have some tree-like structure to it, because of the (high-dimensional) locality it exhibits.) T -- Without geometry, life would be pointless. -- VS
Mar 24
parent dlangPupil <x x989898998.com> writes:
On Friday, 24 March 2017 at 17:48:35 UTC, H. S. Teoh wrote:

 (In my case, though, B-trees may not represent much of an 
 improvement, because I'm dealing with high-dimensional data 
 that cannot be easily linearized to take maximum advantage of 
 B-tree locality. So at some level I still need some kind of 
 hash-like structure to work with my data. But it will probably 
 have some tree-like structure to it, because of the 
 (high-dimensional) locality it exhibits.)


 T
Hi T, Your problem is intriguing and definitely stretching my mind! I'll be factoring your ideas into my app design as I go along. Some techniques that might be relevant to your app, if only for relative performance comparisons, might be: Using metadata in lieu of actual data to maximize the number of rows "represented" in the caches. Using one or more columnstores, both the intra- and extra-cache, to allow transformations of one or more fields of one or more rows with extremely small read, computation and write costs. Scaling the app horizontally, if possible. Using stored procedures on a a SQL NoSQL or NewSQL DBMS to harness the DBMS's bulk-processing and high-throughput capabilities. I'd love to hear whatever details you can share about your app. Alternatively I made a list of a dozen or so questions that would help me think about how to approach your problem. If you're interested in pursuing either avenue, let me know! Thanks again
Mar 24
prev sibling parent reply =?UTF-8?B?Tm9yZGzDtnc=?= <per.nordlow gmail.com> writes:
On Wednesday, 22 March 2017 at 20:00:56 UTC, dlangPupil wrote:
 Hello to all!  As a (D, and coding and forum) newbie I'm 
 learning about D's associative arrays (AAs), and their tiny 
 latency regardless of AA size. Cool!
Where can this be read? Is there a naming for this particular implementation of an AA?
Mar 23
parent dlangPupil <x x989898998.com> writes:
On Thursday, 23 March 2017 at 20:09:46 UTC, Nordlöw wrote:
...
 Where can this be read? Is there a naming for this particular 
 implementation of an AA?
Hi Nordlow, Associative Arrays are introduced in Ali Çehreli's great book, Programming in D – Tutorial and Reference, Ch. 28; and in Section 1.4 of Andrei Alexandrescu's equally great "The D Programming Language." Ali's book is at http://ddili.org/ders/d.en/aa.html The particular data structure I'd like to implement is not a simple hash, but rather a mixture of relational, key-value, columnstore and document database structures. I"ll share it after I've "hashed" it out, and thought of a cool name for it!
Mar 23