How much memory may a HPPL program use on a G2?

[jte]

(09-17-2023 08:09 AM)komame Wrote:  ⋮
This is almost the final version now, as I'm running out of ideas for optimizations. The current results are as follows (measurements only for G2):

??e??r??? --> 386 words found in 5.6 - 7.6s (previously 9 - 11s)
??e??r??s --> 130 words found in 5.7 - 7.7s (previously 7.4 - 8.7s)
??e?????s --> 1031 words found in 5.8 - 7.3s (previously 8.6 - 12s)

p?e??r??? --> 93 words forund in 1.3 - 2.0 (previously 2.6s)
sc???r??? --> 9 words found in 1.0 - 1.3 (previously 1.2s - 1.4s)
⋮

One possibility I was going to mention, when reading the following, was that multiple sort orders could be used so that binary search could be employed even when the search pattern started with “?”. (N sort orders for N-letter words would be the obvious one, although letter pairs come next to mind [although only half of those would be needed — N(N-1)/2 instead of N(N-1). If that’s too much precomputation, letter clumps are another approach – this could still help limit the linear traversal.)

(09-13-2023 12:09 PM)komame Wrote:  ⋮
Later, I realized that such iteration was also unnecessary because since I have a sorted dictionary, I could implement binary search (reducing the search range). This greatly sped up the program
⋮

But I didn’t write that earlier as it seemed precomputation wasn’t of direct interest, based on the following:

(09-13-2023 12:09 PM)komame Wrote:  ⋮
So, this approach would require us to maintain two dictionaries because converting text to binary for a 9-letter dictionary with over 50,000 words would take a very long time with each run (involving a lot of bitwise AND/OR/BITSL operations).
⋮

My first thought with these sorts of things is that there are distinct phases. Phase 1 is setting things up: getting the dictionary, getting it into the program [writing the program…], setting up search data structures, etc. — the performance clock isn’t engaged yet! Phase 2 is benchmarking: running the code against a performance meter. (So, with the example above, the “converting text to binary” isn’t part of “benchmark time”; it would not be done with each run, but be part of “set up”.)

Hmmmm… if the sorting is being done during “benchmark time”, perhaps an alternative sort could still be used, based on the search string. (But perhaps keeping the dictionary sorted [with a conventional sort] is allowed as precomputation / considered to be a fundamental part of what it means to be “a dictionary”.)

It’s nice to see thought-provoking programs!