On Saturday, 24 June 2023 at 12:05:26 UTC, Jonathan M Davis wrote:
On Saturday, June 24, 2023 1:43:53 AM MDT Cecil Ward via
Digitalmars-d-learn wrote:
On Saturday, 24 June 2023 at 07:36:26 UTC, Cecil Ward wrote:
> [...]
I just realised something, your point about altering the table
and having to rehash, is well taken. I hadn’t considered that.
The reason for my foolishness in failing to realise that I’m
asking the impractical is my pattern of usage. I add all the
entries into the mapping table and have no interest in any
lookups until it is fully built. Then a second function starts
to do lookups while the data remains unchanging and that usage
pattern can be guaranteed. I could even idup it if that would
help, as copying < 32 uints wouldn’t take forever. A typical
value would be a mere 5 or less. I only picked 32 to be
completely safely ott.
Well, if the key were a struct or a class, the hashing function
would be opHash. For built-in types, the runtime has hashing
functions that it uses. Either way, with AAs, you really don't
worry about managing the memory, because it's completely
outside of your control. You just put the elements in there
using their associated keys, and if you want to try to speed it
up after you've populated it, you use rehash so that the
runtime can try to move the elements around within the
container so that lookup speeds will be closer to optimal.
As such, for the most part, when dealing with AAs and worrying
about efficiency, the question really becomes whether AAs are
the correct solution rather than much of anything having to do
with how you manage their memory.
With so few elements, it's also possible that using
std.algorithm.searching.find would be faster - e.g. having a
dynamic array of strings where the matching int is at the same
index in a dynamic array of ints - or you could use
std.typecons.Tuple!(string, int)[] with something like
arr.find!(a => a[0] == key)() to find the tuple with the int
you want.
Simply comparing a small number of strings like that might be
faster than what goes on with hashing the string and then
finding the corresponding element within the AA - or it might
not be. You'd have to test that to know. The AA would
definitely be faster with a large number of elements, but with
a small number of elements, the algorithmic complexity doesn't
really matter, and the extra overhad with the AA lookups could
actually mean that the search through the dynamic array is
faster even though it's O(n). But you can only know which is
faster by testing it out with the actual data that you're
dealing with.
Regardless, you need to remember that associative arrays are
not arrays in the C sense. Rather, they're hash tables, so they
function very differently from dynamic arrays, and the rehash
function is the closest that you're going to get to affecting
how the elements are laid out internally or how much memory the
AA is using.
- Jonathan M Davis
I started out looking into a number of runtime library routines,
but in the end it seemed quicker to roll my own code for a crude
recursive descent parser/lexer that parses part of D’s grammar
for expressions, and (again partial grammar) parser for string
literal expressions and so on. I find certain special elements
and execute actions which involve doing the AA lookup and
replacing variable names with ordinal numbers in decimal in the
output stream. Admission: The parsing is the thing that has to be
fast, even though again the size of the D language text is not
likely to be huge at all. But 40 years ago, I came from a world
with 2k RAM and 0.9 MHz clock rates so I have developed a habit
of always thinking about speed before I do anything, needful or
not, to be honest. I once wrote a program that took 35 mins to
evaluate 2+2 and print out the answer, so I’m now ashamed of
writing slow code. Those were bad days, to be honest. 4 GHz+ and
ILP is nicer.
