
"What is a bucket?" ... A question asked during a recent programming course, and probably not one to answer along the lines of "an open topped plastic or metal receptacle to catch, hold or transport water, sand or other materials." In programming terms, a bucket is a software unit of memory allocation, often on the heap - very much more that a bit or a byte. [OK - perhaps I had better explain "heap" too!]
Programs need to dynamically allocate memory to store data as they run - for as a program is written, the programmer won't know how much data may be used in due course through the program at any one time. So the variable storage memory is usually arranged into a
symbol table which holds the names of the variables currently in use, and an address where the values associated with may be found, and a
heap which is where the actual values are held. The heap can grow in size as the program runs, so that there's no need in modern languages to code with limits and fixed sizes, and heap memory can also be released (when a variable isn't needed any more or has shrunk in size) for re-use by other variables. [Due to operating system constraints, the heap can't usually shrink].
If all this clever heap 'stuff' was done by allocating memory on a byte by byte basis, more space and time would be taken up administering the memory use than doing the actual work, so the allocation is typically done using larger units - and each of these larger units is called a
bucket
You rarely see bucket allocation details, even as a programmer - it's too low level. But one of the places that you can see it is within Perl's hashes - if you refer to a hash in a scalar context, you'll get a result like
3/8
which means that the hash has 8 buckets allocated to it, and of those three are currently occupied with data. It's also interesting to watch as a perl hash grows, and see the hashtable being resizes as it gets almost full, with the number of buckets allocated being doubled and redoubled ...
for ($k=1; $k<4000; $k++) {
$fing{$k} = $k + 55;
print ("$k - ",($n = %fing),"\n");
}
gives the following results:
1 - 1/8
2 - 2/8
3 - 3/8
4 - 3/8
5 - 4/8
6 - 5/8
7 - 6/8
8 - 7/16
9 - 8/16
10 - 9/16
11 - 10/16
12 - 10/16
13 - 10/16
14 - 11/16
15 - 11/16
16 - 14/32
17 - 14/32
18 - 15/32
Finally, it's interesting to note a considerable increase in the number of buckets occupied each time the size of the hash is increased, indicative of the use of a longer hash key as the size of the hash table increases.
This code - in a complete example - is available
[here]. The image is adapted from
Free Clipart Now - "a large collection of high quality, public domain clipart graphics for presentations, web pages, documents, emails...".
(written 2010-12-26, updated 2011-01-03)
Associated topics are indexed as below, or enter http://melksh.am/nnnn for individual articles
P211 - Perl - Hashes [240] Conventional restraints removed - (2005-03-09)
[386] What is a callback? - (2005-07-22)
[738] (Perl) Callbacks - what are they? - (2006-05-30)
[930] -> , >= and => in Perl - (2006-11-18)
[968] Perl - a list or a hash? - (2006-12-06)
[1334] Stable sorting - Tcl, Perl and others - (2007-09-06)
[1705] Environment variables in Perl / use Env - (2008-07-11)
[1826] Perl - Subs, Chop v Chomp, => v , - (2008-10-08)
[1856] A few of my favourite things - (2008-10-26)
[1917] Out of memory during array extend - Perl - (2008-12-02)
[2833] Fresh Perl Teaching Examples - part 2 of 3 - (2010-06-27)
[2836] Perl - the duplicate key problem explained, and solutions offered - (2010-06-28)
[2915] Looking up a value by key - associative arrays / Hashes / Dictionaries - (2010-08-11)
[2920] Sorting - naturally, or into a different order - (2010-08-14)
[3042] Least Common Ancestor - what is it, and a Least Common Ancestor algorithm implemented in Perl - (2010-11-11)
[3072] Finding elements common to many lists / arrays - (2010-11-26)
[3400] $ is atomic and % and @ are molecular - Perl - (2011-08-20)
[3451] Why would you want to use a Perl hash? - (2011-09-20)
[3662] Finding all the unique lines in a file, using Python or Perl - (2012-03-20)
Some other Articles
The days after ChristmasA weighty decisionMy First ChristmasHotel and Training Course prices - the effect of the VAT rise on 4th January 2011BucketsAdventure with references to lists and lists of referencesCatering in Syracuse, the Saigon Cafe, stolen images and ChristmasThank you - and Happy ChristmasAND and OR operators - what is the difference between logical and bitwise varieties?The week before Christmas