shared_rhash_t Derived Type

type, public :: shared_rhash_t

The shared read-only hash table stores a given number of arbitrary input values in one contiguous array and addresses this contiguous array using a hashtable The input values are stored in order of ascending hash value, with conflicts stored adjacently. For each hash value, the position of the first value with that hash value is stored. The lookup then searches for a given value between the first and the last stored value with the same hash value.


Components

Type Visibility Attributes Name Initial
type(shared_array_int64_t), private :: indices
type(shared_array_int64_t), private :: hval_offsets
integer(kind=int64), private :: hval_range
integer, private, allocatable :: mult(:)
logical, private :: t_conflicts_known = .false.

Type-Bound Procedures

procedure, public :: alloc

  • private subroutine alloc(this, n_elem, htsize)

    Allocate the internal (shared) memory

    Arguments

    Type IntentOptional Attributes Name
    class(shared_rhash_t), intent(inout) :: this
    integer(kind=int64), intent(in) :: n_elem

    number of distinct values to store
    integer(kind=int64), intent(in) :: htsize

    range of the hash function

procedure, public :: dealloc

  • private subroutine dealloc(this)

    Deallocate all arrays associated with this hash table object

    Arguments

    Type IntentOptional Attributes Name
    class(shared_rhash_t), intent(inout) :: this

procedure, public :: count_value

  • private subroutine count_value(this, hval)

    Log the occurence of this hash value in the set of values to be stored Does not add it, only updates the offsets

    Arguments

    Type IntentOptional Attributes Name
    class(shared_rhash_t), intent(inout) :: this
    integer(kind=int64), intent(in) :: hval

    hash value to be logged

procedure, public :: add_value

  • private subroutine add_value(this, hval, index, pos)

    Add an input value to the stored values, assuming we already know the offsets

    Arguments

    Type IntentOptional Attributes Name
    class(shared_rhash_t), intent(inout) :: this
    integer(kind=int64), intent(in) :: hval

    value to be stored
    integer(kind=int64), intent(in) :: index

    value to be stored index belonging to this value
    integer(kind=int64), intent(out) :: pos

    on return, the position where this value was stored

procedure, public :: finalize_setup

  • private subroutine finalize_setup(this)

    Dealloates temporary arrays used for initialisation

    Arguments

    Type IntentOptional Attributes Name
    class(shared_rhash_t), intent(inout) :: this

procedure, public :: setup_offsets

  • private subroutine setup_offsets(this)

    For performance reasons, we cannot directly calculate the offsets, but instead first count the number of conflicts per hash value. Then, we sum these up cumulatively Directly counting the offsets is horrifically slow

    Arguments

    Type IntentOptional Attributes Name
    class(shared_rhash_t), intent(inout) :: this

procedure, public :: direct_lookup

  • private subroutine direct_lookup(this, hval, index, pos, t_found)

    Look up a value in this hash table. Returns whether the value is stored and if yes, where

    Arguments

    Type IntentOptional Attributes Name
    class(shared_rhash_t), intent(in) :: this
    integer(kind=int64), intent(in) :: hval

    value to be looked up hash value of the index to look up
    integer(kind=int64), intent(in) :: index

    value to be looked up
    integer(kind=int64), intent(out) :: pos

    on return, the position of index if found, else 0
    logical, intent(out) :: t_found

    on return, true if and only if index was found

procedure, public :: callback_lookup

  • private subroutine callback_lookup(this, hval, pos, t_found, loc_verify)

    Generic lookup routine, using an external routine for verification DOES NOT TO THE SAME AS direct_lookup

    Arguments

    Type IntentOptional Attributes Name
    class(shared_rhash_t), intent(in) :: this
    integer(kind=int64), intent(in) :: hval

    hash value of the index to look up
    integer(kind=int64), intent(out) :: pos

    on return, the matching entry
    logical, intent(out) :: t_found

    on return, true if and only if index was found
    private function loc_verify(i) result(match)
    Arguments
    Type IntentOptional Attributes Name
    integer(kind=int64), intent(in) :: i
    Return Value logical

procedure, public :: known_conflicts

  • private function known_conflicts(this) result(t_kc)

    During initialisation, we can only start writing values once the offsets are known. This requires knowledge about the number of conflicts per hash value. This function tells us whether the conflicts have already been counted.

    Arguments

    Type IntentOptional Attributes Name
    class(shared_rhash_t), intent(in) :: this

    Return Value logical

procedure, public :: val_range

  • private function val_range(this) result(h_range)

    Get the range of hash table values of this ht

    Arguments

    Type IntentOptional Attributes Name
    class(shared_rhash_t), intent(in) :: this

    Return Value integer(kind=int64)

procedure, public :: sync

  • private subroutine sync(this)

    Synchronize the shared resource

    Arguments

    Type IntentOptional Attributes Name
    class(shared_rhash_t), intent(inout) :: this

Source Code

    type :: shared_rhash_t
        ! All arrays here are mpi-3 shared memory
        private
        ! The hashed data is stored in one contiguous array
        ! Typically, we will be storing indices of some array
        type(shared_array_int64_t) :: indices

        ! Alongside, we store the offset of the hash values - the position of the first
        ! index for each hash value
        type(shared_array_int64_t) :: hval_offsets
        ! The range of the hash function
        integer(int64) :: hval_range

        ! auxiliary array for initialisation. This stores how many input values we already
        ! added for each hash value
        integer, allocatable :: mult(:)

        ! are the conflicts of the hashtable already counted (have the offsets been set?)
        logical :: t_conflicts_known = .false.

    contains

        ! Allocate the memory
        procedure :: alloc
        procedure :: dealloc
        ! Fill up the indices - since this is memory critical, we allow direct write to them
        procedure :: count_value
        procedure :: add_value
        ! Set up the table. It is read-only, so this is the only way to set it up
        procedure :: finalize_setup
        ! After counting the indices, we have to get the offsets (doing so on the fly is
        ! horiffically slow)
        procedure :: setup_offsets

        ! Look up an index. Returns the position in the contiguous array
        procedure :: direct_lookup
        procedure :: callback_lookup

        ! Tell if the conflicts have been counted
        procedure :: known_conflicts
        ! Check how large the hash table shall be
        procedure :: val_range

        ! Synchronize between tasks
        procedure :: sync
    end type shared_rhash_t