Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Re^3: Does "preallocating hash improve performance"? Or "using a hash slice"?

by BrowserUk (Patriarch)
on Feb 20, 2017 at 18:14 UTC ( [id://1182367]=note: print w/replies, xml ) Need Help??


in reply to Re^2: Does "preallocating hash improve performance"? Or "using a hash slice"?
in thread Does "preallocating hash improve performance"? Or "using a hash slice"?

you missed vr's point about hash slices.

Not so much "missed it" as chose not to address it.

With @h{ @keys } = @values; perl could use the size of the keys list to preallocate the hash

The problem with that is that in order to gain the 18% saving from the preallocation of my 10,000,000 key hash, the hash slice would:

  1. Allocate stack space to accommodate 20,000,000 items on the stack.
  2. Turn the 10,000,000 element array, @keys, into a 10,000,000 item list on the stack.
  3. Turn the 10,000,000 element array, @values, into a 10,000,000 item list also the stack.
  4. Process those two lists in parallel adding each key/value pair individually; doubling (and redoubling), hashing (and rehashing) as required.
  5. Free the space required to accommodate the 20,000,000 items on the stack back to the memory pool.

It's a lot more complicated than that, but it is sufficiently accurate to make my point.)

So, now the process not only has two copies of all the keys and values (in the arrays as well as the hash), it also has allocated enough space to store them all again on the stack.

So that means the peak memory usage required to do the slice assignment is at least 4 times more than is eventually required to construct the hash itself; and the hash was not preallocated either!

Slice assignment can be more efficient for relatively small hashes provided it is necessary to the rest of the code to have the keys and values stored in arrays as well. But if you are loading them into arrays, simply so that you can use list assignment to construct a hash from them, it is a disaster in terms of both memory usage and processing time.

And for anything larger then pretty modest sized hashes ( a few 10s or low 100s of key/value pairs) then the cost (memory and time) of building the two lists on the stack far outweights any gain from moving the loop into C. Especially as the potential of having the hash pre-sized doesn't happen. (It probably could, but it doesn't.)


With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.
In the absence of evidence, opinion is indistinguishable from prejudice.
.

Replies are listed 'Best First'.
Re^4: Does "preallocating hash improve performance"? Or "using a hash slice"?
by Eily (Monsignor) on Feb 21, 2017 at 10:15 UTC

    I hope perl is not so inefficient that it copies all the content of a list when it needs to process it, when simply pointing to the already allocated elements would be enough. Even more so with arrays. I'd also expect some COW mechanism to remove a lot of allocating and copying. Keys might be more trouble though, as all data stored in them have to be stringified first (and I wouldn't be surprised to learn that hash keys always hold a copy of the initial string, since as far as I can tell they are not standard scalar values). I agree that the memory usage, and number of copies is certainly higher when you go all the way to slicing, but I don't expect "at least 4 times more" memory. Actually I remember finding out in a post a while ago that having the keys and values in two arrays takes more place than just having them in a hash (which kind of makes sense, order is extra information, although technically I think it's because keys can afford to just be strings, without all the extras of ordinary scalar values)

    Not so much "missed it" as chose not to address it.
    Well that's too bad, you did have an interresting answer: that if you need to gather your data in some form before populating your hash, you shouldn't expect to obtain the best result memory-wise and time-wise (because of the copies). So you probably don't need to worry about preallocation if you don't need to worry about slicing.

      Okay, let me try responding to this again. Blow by blow this time.

      I hope perl is not so inefficient that it copies all the content of a list when it needs to process it, when simply pointing to the already allocated elements would be enough.
      • "Hoping"

        Doesn't change anything.

      • "perl is not so inefficient"

        AFAIK: Perl(5) is still more efficient (for most things) than other similar languages (Python, Ruby, BASH, CMD, Powershell etc.); in part because of the efficiency (minimalism) of its runloop and stack-based opcodes.

        However, it is less efficient than (uncompiled) Java or Javascript or Julia etc.; in part because of its stack-based opcodes.

        The stack-based opcodes lend themselves to "efficient dispatch" when running as a pure bytecode interpreter; but they do not lend themselves to great efficiency gains through JIT compilation.

        The J-languages were either designed from the outset (Julia) or have evolved over time under corporate sponsership (Java & Javascript), to lend themselves to efficient JIT compilation at runtime. Perl has not.

      • "that it copies all the content of a list when it needs to process it"

        I didn't say anything about "copying ... a list". I said: "Turn the ... array, ... into a ... list".

        Perl's opcodes are stack based. All arguments are passed on the (perl! Not C) stack. The arguments to an array assignment: @{ @keys } = @values; are the two arrays @keys & @values. These are passed to the opcode on the stack.

        The process of converting an array to a list on the stack is not a copy operation per se; but rather an aliasing operation. The original SVs in the array are not copied, but their address are pushed onto the stack. A 10 million element array, results in 10 million SV*s being pushed to the stack.

        Space for those 10 million SV*s has to be allocated; and all the stack pointers and the associated "Mark stack" -- another stack that manages the Perl stack see illustration -- have to be maintained and updated.

        Ditto for the second argument array (@values). So, the process is not a "copy operation", but neither is it trivial.

      • "when simply pointing to the already allocated elements would be enough."

        It does "simply point"; but it points at each of the 20 million elements individually.

        Couldn't this be changed to simply stack 2 pointers, one to each of the two arrays?

        Yes, if the arguments to the array assignment are both arrays, but what about this: @hash{ 1, @small, 10 .. 25, @more } = @array[ reverse 0 .. $#array ];

        The point of that contrived example is to show that the destination and sources lists of a, more properly termed list assignment (though known internally as array assignment), can be made up of elements drawn from (any combination of) array and hash elements, constants, ordinary scalars, slices of arrays or hashes etc.

        So, for those occasions when the destination list is entirely defined by one array, and the source list entirely defined by another array, it would be possible to only pass references to those two arrays on the stack, and thus avoid large scale allocations; but is would require special casing, and probably another opcode.

      Even more so with arrays.

      Um. The example contains arrays. So if the previous sentence was not talking about arrays, what was it talking about?

      I'd also expect some COW mechanism to remove a lot of allocating and copying.

      CopyOnWrite generally applies to entire data segments of a process that is cheaply shared with another process; that's obviously not applicable here.

      Perl does have some internal flags and references with "COW" in their names; where by the copying of scalars is avoided (by aliasing) until and unless they are written to; but as the argument lists (destination & source) to op_aassign are inherently readonly, that does not apply here either.

      Keys might be more trouble though, as all data stored in them have to be stringified first (and I wouldn't be surprised to learn that hash keys always hold a copy of the initial string, since as far as I can tell they are not standard scalar values).

      Since CoW is not applicable to the destination and source lists; most of that is irrelevant, but I can confirm that hash keys are not normal scalars, and even if they are already in memory as scalars, the text will be copied into the HV structure.

      I agree that the memory usage, and number of copies is certainly higher when you go all the way to slicing, but I don't expect "at least 4 times more" memory.

      For the statement: @hash{ @keys } = @array; here is the memory usage:

      C:\test>p1 print mem;; 9,356 K $#keys = 10e6; $#values = 10e6; $keys[ $_ ] = "$_", $values[ $_ ] = $_ + for 0 .. 10e6;; print mem;; 2,000,088 K @hash{ @keys } = @values;; print mem;; 4,394,716 K print size( \%hash );; 783106748

      So, final memory usage: 4,394,716 K - initial memory usage: 9,356 K = memory used by the two arrays, the final hash and all the intermediate allocations for the stack, smaller versions of the hash during construction and other bits & bobs: 4,385,360 K or 4490608640 bytes.

      And, 4490608640 / 783106748 = 5.734350586901084908030954676437. Your expectations are wrong.

      I can't see any value going further.


      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.
      In the absence of evidence, opinion is indistinguishable from prejudice.

        Going farther has been rather enlightening for me, i never realized what keys %h = 10e6; would do or that apparently $#h = 10e6; would do the same, and i am known to read the documentation at times just because im bored. I did look up the keys %h = 10e6; reference in the doc after you used it tho.

        so thanks

        I can't see any value going further.

        I actually wasn't expecting you to get back on that explanation with so much detail and technical information, so thanks for that.

        The part I got wrong is that I thought you meant that all the data (all the strings, not just the SV*s) was duplicated four times; this is also why I started talking about COWs, because I didn't understand why perl would need to copy the strings so many times. I got confused by "two copies of all the keys and values" where I failed to understand that "keys and values" was refering to their SV*s. So by "4 times more memory", I meant 4 times more than the total_size of the hash, not just the structure size.

        So, for those occasions when the destination list is entirely defined by one array, and the source list entirely defined by another array, it would be possible to only pass references to those two arrays on the stack, and thus avoid large scale allocations; but is would require special casing, and probably another opcode.

        This was what my "even more so with arrays" was about, I didn't understand the need to have all the data duplicated so often. Again, it's the "all the data" I got wrong. Indeed my post doesn't make much sense starting from that point.

        Your expectations are wrong.

        Clearly I've been underestimating the proportion of structure data over actual data. Though you did say yourself that keys strings are always copied into the hash. But they are not allocated or copied 4 times. With $keys[ $_ ] = "$_" x 20 in your code (so strings with a mean length around 100 characters) I get:

        8 096 Ko 3 228 772 Ko 6 396 092 Ko 2091995858
        Where 6396092*1024/2091995858 = 3.131.

        Thanks again for taking the time to detail your answer.

        Nb: I got the mem sub in BrowserUK's post here if anyone is interested. The numbers are separated by \xFF (not a space) so /(\S+ Ko)$/ worked for me.

      I hope perl is not so inefficient that it copies all the content of a list when it needs to process it,

      Hoping doesn't change anything; I described what the code (perl sources) actually do; it is your choice whether to believe me or not.

      You could always check for yourself:

      Well that's too bad,

      Oh, sorry. I wasn't aware you had joined the Answers Approval Subcommittee?

      if you need to gather your data ...

      Are you sure that what I said?


      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.
      In the absence of evidence, opinion is indistinguishable from prejudice.
        Hoping doesn't change anything;

        Fair enough.

        I wasn't aware you had joined the Answers Approval Subcommittee?

        I'm planning on leaving, they still didn't deliver the cookies. That (the "too bad" part) was clumsy of me, sorry. I'm not sure how offensive (or line-crossing) my answer is because I may not get all the implications of my formulation. I do understand that I don't get to judge your decision not to post something.

        Are you sure that what I said?

        Even less so now that you ask that. I was trying to make sense of your answer in the context of this thread, clearly I got the wrong message.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1182367]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others learning in the Monastery: (3)
As of 2024-03-29 02:02 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found