src/share/vm/utilities/hashtable.cpp
Index Unified diffs Context diffs Sdiffs Wdiffs Patch New Old Previous File Next File

## src/share/vm/utilities/hashtable.cpp

Print this page

    *** 33,42 ****
    --- 33,86 ----
      #include "utilities/dtrace.hpp"
      #include "utilities/hashtable.hpp"
      #include "utilities/hashtable.inline.hpp"
      #include "utilities/numberSeq.hpp"

    + // ------------------------------------------------------------------------------------------
    + //
    + // start of next_prime
    + //
    + // http://stackoverflow.com/questions/4475996/given-prime-number-n-compute-the-next-prime
    + //
    + bool is_prime(int x)
    + {
    +     int o = 4;
    +     for (int i = 5; true; i += o)
    +       {
    +           int q = x / i;
    +           if (q < i)
    +               return true;
    +           if (x == q * i)
    +               return false;
    +           o ^= 6;
    +         }
    +     return true;
    +   }
    + int next_prime(int x)
    + {
    +     switch (x)
    +     {
    +           case 0:
    +           case 1:
    +           case 2:
    +             return 2;
    +           case 3:
    +             return 3;
    +           case 4:
    +           case 5:
    +             return 5;
    +       }
    +     int k = x / 6;
    +     int i = x - 6 * k;
    +     int o = i < 2 ? 1 : 5;
    +     x = 6 * k + o;
    +     for (i = (3 + o) / 2; !is_prime(x); x += i)
    +         i ^= 6;
    +       return x;
    +   }
    + // end of next_prime
    + // ------------------------------------------------------------------------------------------

      // This hashtable is implemented as an open hash table with a fixed number of buckets.

      template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry_free_list() {
        BasicHashtableEntry<F>* entry = NULL;
    *** 73,82 ****
    --- 117,127 ----
      template <class T, MEMFLAGS F> HashtableEntry<T, F>* Hashtable<T, F>::new_entry(unsigned int hashValue, T obj) {
        HashtableEntry<T, F>* entry;

        entry = (HashtableEntry<T, F>*)BasicHashtable<F>::new_entry(hashValue);
        entry->set_literal(obj);
    +   entry->_debug_lookups = 0;
        return entry;
      }

      // Check to see if the hashtable is unbalanced.  The caller set a flag to
      // rehash at the next safepoint.  If this bucket is 60 times greater than the
    *** 152,161 ****
    --- 197,354 ----
          }
          _buckets = NULL;
        }
      }

    + // Resize the internal bucket table if the current one reaches its maximum allowed chain length (LoadFactor)
    + template <MEMFLAGS F> ResizeHashtableStats BasicHashtable<F>::resize_table(Monitor* lock, float trigger, float desired) {
    +   assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint");
    +   assert(lock->is_locked()==false, "table lock must not be held");
    +
    +   ResizeHashtableStats stats = {false, 0, 0};
    +
    + //#define FORCE_RESIZE
    + #ifdef FORCE_RESIZE
    +   int force_mod = 3;
    +   if (((_debug_resize_fire++) % force_mod) != 0) {
    +     return stats;
    +   }
    + #else // FORCE_RESIZE
    +   // Check if there is anything to be done here
    +   float load_factor = (float)_number_of_entries/(float)_table_size;
    +   if (load_factor < trigger) {
    +     return stats;
    +   }
    + #endif // FORCE_RESIZE
    +
    + #ifndef PRODUCT
    + //#ifdef PRODUCT_TEST
    +   julong time = (julong)os::javaTimeNanos();
    + #endif // PRODUCT
    +
    +   MutexLocker mu(lock);
    +
    +   if (HashtablesVerifyBeforeResize == true) {
    +     verify();
    +   }
    +
    +   // Find the next best size for the hashtable.
    +   int table_size_old = _table_size;
    + #ifdef FORCE_RESIZE
    +   int table_size_new = next_prime(table_size_old+1);
    + #else
    +   int table_size_new = next_prime((int)(((float)_number_of_entries/(float)desired)+0.5f));
    + #endif // FORCE_RESIZE
    +
    +   // Allocate new buckets and clear them
    +   HashtableBucket<F>* buckets_new = NEW_C_HEAP_ARRAY2(HashtableBucket<F>, table_size_new, F, CURRENT_PC);
    +   if (buckets_new == NULL) {
    +     return stats;
    +   }
    +
    +   for (int i = 0; i < table_size_new; i++) {
    +     buckets_new[i].clear();
    +   }
    +
    +   // hash_to_index() uses _table_size, so switch the sizes now
    +   _table_size = table_size_new;
    +
    +   // Do not bother sorting if new size is bigger than the number of entries
    +   bool sort = HashtablesResizeSort && (table_size_new > _number_of_entries);
    +
    +   // Move entries from the old table to a new table
    +   for (int index_old = 0; index_old < table_size_old; index_old++) {
    +     for (BasicHashtableEntry<F>* p = _buckets[index_old].get_entry(); p != NULL; ) {
    +       BasicHashtableEntry<F>* next = p->next();
    +       bool keep_shared = p->is_shared();
    +
    +       int index_new = hash_to_index(p->hash());
    +
    +       if (sort == true) {
    +         // Insert according to the lookup counter value, higher scored entries go to the front
    +         BasicHashtableEntry<F>* p_new_bigger = NULL;
    +         for (BasicHashtableEntry<F>* p_new = buckets_new[index_new].get_entry(); p_new != NULL; p_new = p_new->next()) {
    +           if (p_new != NULL) {
    +             if (p_new->_debug_lookups > p->_debug_lookups) {
    +               p_new_bigger = p_new;
    +             } else {
    +               break;
    +             }
    +           }
    +         }
    +         BasicHashtableEntry<F>* p_new_bigger_next = NULL;
    +         if (p_new_bigger == NULL) {
    +           p_new_bigger_next = buckets_new[index_new].get_entry();
    +           buckets_new[index_new].set_entry(p);
    +         } else {
    +           p_new_bigger_next = p_new_bigger->next();
    +           p_new_bigger->set_next(p);
    +         }
    +         p->set_next(p_new_bigger_next);
    +       } else {
    + //#define ADD_TO_END
    + #ifdef ADD_TO_END
    +         BasicHashtableEntry<F>* p_new_last = NULL;
    +         for (BasicHashtableEntry<F>* p_new = buckets_new[index_new].get_entry(); p_new != NULL; p_new = p_new->next()) {
    +           p_new_last = p_new;
    +         }
    +         if (p_new_last == NULL) {
    +           buckets_new[index_new].set_entry(p);
    +         } else {
    +           p_new_last->set_next(p);
    +         }
    +         p->set_next(NULL);
    + #else // ADD_TO_END
    +         p->set_next(buckets_new[index_new].get_entry());
    +         buckets_new[index_new].set_entry(p);
    + #endif // ADD_TO_END
    +       }
    +
    +       if (keep_shared) {
    +         p->set_shared();
    +       }
    +       p = next;
    +     }
    +   }
    +
    +   // The old backets now can be released
    +   BasicHashtable<F>::free_buckets();
    +
    +   // Switch to the new storage
    +   _buckets = buckets_new;
    +
    +   if (HashtablesVerifyAfterResize == true) {
    +     verify();
    +   }
    +
    + #ifndef PRODUCT
    + //#ifdef PRODUCT_TEST
    +   julong duration = (julong)os::javaTimeNanos() - time;
    +
    +   // Reset new table's statistics
    +   _debug_lookup_count = 0;
    +   _debug_insertion_count = 0;
    +   _debug_lookup_found_count = 0;
    +   _debug_lookup_found_max_duration = 0;
    +   _debug_lookup_found_total_duration = 0;
    +   _debug_chain_found_maximum_length = 0;
    +   _debug_chain_found_total_length = 0;
    +   _debug_lookup_failed_count = 0;
    +   _debug_lookup_failed_max_duration = 0;
    +   _debug_lookup_failed_total_duration = 0;
    +   _debug_chain_failed_maximum_length = 0;
    +   _debug_chain_failed_total_length = 0;
    +   _debug_resize_max_duration = (duration > _debug_resize_max_duration) ? duration : _debug_resize_max_duration;
    +   _debug_resize_total_duration += duration;
    +   _debug_resize_total_count++;
    + #endif // PRODUCT
    +
    +   stats.resized = true;
    +   stats.old_size = table_size_old;
    +   stats.new_size = table_size_new;
    +   return stats;
    + }

      // Reverse the order of elements in the hash buckets.

      template <MEMFLAGS F> void BasicHashtable<F>::reverse() {

    *** 203,214 ****
            p->set_shared();
          }
        }
      }

    -
    -
      // Reverse the order of elements in the hash buckets.

      template <class T, MEMFLAGS F> void Hashtable<T, F>::reverse(void* boundary) {

        for (int i = 0; i < this->table_size(); ++i) {
    --- 396,405 ----
    *** 237,264 ****
            *bucket_addr(i) = high_list;
          }
        }
      }

    ! template <class T, MEMFLAGS F> int RehashableHashtable<T, F>::literal_size(Symbol *symbol) {
        return symbol->size() * HeapWordSize;
      }

    ! template <class T, MEMFLAGS F> int RehashableHashtable<T, F>::literal_size(oop oop) {
        // NOTE: this would over-count if (pre-JDK8) java_lang_Class::has_offset_field() is true,
        // and the String.value array is shared by several Strings. However, starting from JDK8,
        // the String.value array is not shared anymore.
        assert(oop != NULL && oop->klass() == SystemDictionary::String_klass(), "only strings are supported");
        return (oop->size() + java_lang_String::value(oop)->size()) * HeapWordSize;
      }

      // Dump footprint and bucket length statistics
      //
      // Note: if you create a new subclass of Hashtable<MyNewType, F>, you will need to
      // add a new function Hashtable<T, F>::literal_size(MyNewType lit)

    ! template <class T, MEMFLAGS F> void RehashableHashtable<T, F>::dump_table(outputStream* st, const char *table_name) {
        NumberSeq summary;
        int literal_bytes = 0;
        for (int i = 0; i < this->table_size(); ++i) {
          int count = 0;
          for (HashtableEntry<T, F>* e = this->bucket(i);
    --- 428,476 ----
            *bucket_addr(i) = high_list;
          }
        }
      }

    ! // Dump the hash table buckets.
    !
    ! template <MEMFLAGS F> void BasicHashtable<F>::copy_buckets(char** top, char* end) {
    !   intptr_t len = _table_size * sizeof(HashtableBucket<F>);
    !   *(intptr_t*)(*top) = len;
    !   *top += sizeof(intptr_t);
    !
    !   *(intptr_t*)(*top) = _number_of_entries;
    !   *top += sizeof(intptr_t);
    !
    !   if (*top + len > end) {
    !     report_out_of_shared_space(SharedMiscData);
    !   }
    !   _buckets = (HashtableBucket<F>*)memcpy(*top, _buckets, len);
    !   *top += len;
    ! }
    !
    ! template <class T, MEMFLAGS F> int Hashtable<T, F>::literal_size(Symbol *symbol) {
        return symbol->size() * HeapWordSize;
      }

    ! template <class T, MEMFLAGS F> int Hashtable<T, F>::literal_size(oop oop) {
        // NOTE: this would over-count if (pre-JDK8) java_lang_Class::has_offset_field() is true,
        // and the String.value array is shared by several Strings. However, starting from JDK8,
        // the String.value array is not shared anymore.
        assert(oop != NULL && oop->klass() == SystemDictionary::String_klass(), "only strings are supported");
        return (oop->size() + java_lang_String::value(oop)->size()) * HeapWordSize;
      }

    + template <class T, MEMFLAGS F> int Hashtable<T, F>::literal_size(Klass *klass) {
    +   return klass->size() * HeapWordSize;
    + }
    +
      // Dump footprint and bucket length statistics
      //
      // Note: if you create a new subclass of Hashtable<MyNewType, F>, you will need to
      // add a new function Hashtable<T, F>::literal_size(MyNewType lit)

    ! template <class T, MEMFLAGS F> void Hashtable<T, F>::dump_table(outputStream* st, const char *table_name) {
        NumberSeq summary;
        int literal_bytes = 0;
        for (int i = 0; i < this->table_size(); ++i) {
          int count = 0;
          for (HashtableEntry<T, F>* e = this->bucket(i);
    *** 282,316 ****
        st->print_cr("%s statistics:", table_name);
        st->print_cr("Number of buckets       : %9d = %9d bytes, avg %7.3f", (int)num_buckets, bucket_bytes,  bucket_avg);
        st->print_cr("Number of entries       : %9d = %9d bytes, avg %7.3f", (int)num_entries, entry_bytes,   entry_avg);
        st->print_cr("Number of literals      : %9d = %9d bytes, avg %7.3f", (int)num_entries, literal_bytes, literal_avg);
        st->print_cr("Total footprint         : %9s = %9d bytes", "", total_bytes);
    !   st->print_cr("Average bucket size     : %9.3f", summary.avg());
        st->print_cr("Variance of bucket size : %9.3f", summary.variance());
        st->print_cr("Std. dev. of bucket size: %9.3f", summary.sd());
        st->print_cr("Maximum bucket size     : %9d", (int)summary.maximum());
      }

    !
    ! // Dump the hash table buckets.
    !
    ! template <MEMFLAGS F> void BasicHashtable<F>::copy_buckets(char** top, char* end) {
    !   intptr_t len = _table_size * sizeof(HashtableBucket<F>);
    !   *(intptr_t*)(*top) = len;
    !   *top += sizeof(intptr_t);
    !
    !   *(intptr_t*)(*top) = _number_of_entries;
    !   *top += sizeof(intptr_t);
    !
    !   if (*top + len > end) {
    !     report_out_of_shared_space(SharedMiscData);
        }
    !   _buckets = (HashtableBucket<F>*)memcpy(*top, _buckets, len);
    !   *top += len;
      }

    -
      #ifndef PRODUCT

      template <class T, MEMFLAGS F> void Hashtable<T, F>::print() {
        ResourceMark rm;

    --- 494,605 ----
        st->print_cr("%s statistics:", table_name);
        st->print_cr("Number of buckets       : %9d = %9d bytes, avg %7.3f", (int)num_buckets, bucket_bytes,  bucket_avg);
        st->print_cr("Number of entries       : %9d = %9d bytes, avg %7.3f", (int)num_entries, entry_bytes,   entry_avg);
        st->print_cr("Number of literals      : %9d = %9d bytes, avg %7.3f", (int)num_entries, literal_bytes, literal_avg);
        st->print_cr("Total footprint         : %9s = %9d bytes", "", total_bytes);
    !   st->print_cr("Average bucket size     : %9.3f (load factor)", summary.avg());
        st->print_cr("Variance of bucket size : %9.3f", summary.variance());
        st->print_cr("Std. dev. of bucket size: %9.3f", summary.sd());
        st->print_cr("Maximum bucket size     : %9d", (int)summary.maximum());
      }

    ! template <class T, MEMFLAGS F> void Hashtable<T, F>::dump(outputStream* st, const char* table_name) {
    ! #ifndef PRODUCT
    ! //#ifdef PRODUCT_TEST
    !   st->print("\n-------------------------------------------------------------------------------\n");
    !   dump_table(st, table_name);
    !   st->print("-------------------------\n");
    !   {
    !     int count = 0;
    !     for (int i=0; i<1024; i++) {
    !       if (this->_debug_table_threads[i] != 0) {
    !         count++;
    !       } else {
    !         break;
            }
    !     }
    !     st->print_cr("Number of threads       : %9d", count);
    !   }
    !   st->print("-------------------------\n");
    !   {
    !     st->print_cr("All Lookups             : %9llu", this->_debug_all_lookup_count);
    !     st->print_cr("All Insertions          : %9llu", this->_debug_all_insertion_count);
    !     double ratio = 0.0;
    !     if (this->_debug_all_lookup_count > 0.0) {
    !       ratio = (double)(this->_debug_all_lookup_count-this->_debug_all_insertion_count) / (double)this->_debug_all_lookup_count;
    !     }
    !     st->print_cr("All Lookups ratio       : %9.3f", 100.0*ratio);
    !   }
    !   st->print("-------------------------\n");
    !   {
    !     st->print_cr("Lookups                 : %9llu", this->_debug_lookup_count);
    !     st->print_cr("Insertions              : %9llu", this->_debug_insertion_count);
    !     double ratio = 0.0;
    !     if (this->_debug_lookup_count > 0.0) {
    !       ratio = (double)(this->_debug_lookup_count-this->_debug_insertion_count) / (double)this->_debug_lookup_count;
    !     }
    !     st->print_cr("Lookups ratio           : %9.3f", 100.0*ratio);
    !   }
    !   {
    !     st->print_cr("Found Lookups           : %9llu", this->_debug_lookup_found_count);
    !     st->print_cr("Failed Lookups          : %9llu", this->_debug_lookup_failed_count);
    !     double ratio = 0.0;
    !     if (this->_debug_lookup_found_count > 0) {
    !       ratio = (double)this->_debug_lookup_found_count / (double)(this->_debug_lookup_found_count+this->_debug_lookup_failed_count);
    !     }
    !     st->print_cr("Found ratio             : %9.3f", 100.0*ratio);
    !   }
    !   st->print("-------------------------\n");
    !   {
    !     double average = 0.0;
    !     if (this->_debug_lookup_found_count > 0) {
    !       average = (((double)this->_debug_lookup_found_total_duration / (double)this->_debug_lookup_found_count) + 0.5);
    !     }
    !     st->print_cr("Total found lookup time : %9llu ns", this->_debug_lookup_found_total_duration);
    !     st->print_cr("Max found lookup time   : %9llu ns", this->_debug_lookup_found_max_duration);
    !     st->print_cr("Avg found lookup time   : %9d ns", (int)average);
    !   }
    !   {
    !     double average = 0.0;
    !     if (this->_debug_lookup_failed_count > 0) {
    !       average = (((double)this->_debug_lookup_failed_total_duration / (double)this->_debug_lookup_failed_count) + 0.5);
    !     }
    !     st->print_cr("Total failed lookup time: %9llu ns", this->_debug_lookup_failed_total_duration);
    !     st->print_cr("Max failed lookup time  : %9llu ns", this->_debug_lookup_failed_max_duration);
    !     st->print_cr("Avg failed lookup time  : %9d ns", (int)average);
    !   }
    !   st->print("-------------------------\n");
    !   {
    !     double average = 0.0;
    !     if (this->_debug_lookup_found_count > 0) {
    !       average = (double)this->_debug_chain_found_total_length / (double)this->_debug_lookup_found_count;
    !     }
    !     st->print_cr("Max found chain length  : %9llu", this->_debug_chain_found_maximum_length);
    !     st->print_cr("Avg found chain length  : %9.3f", average);
    !   }
    !   {
    !     double average = 0.0;
    !     if (this->_debug_lookup_failed_count > 0) {
    !       average = (double)this->_debug_chain_failed_total_length / (double)this->_debug_lookup_failed_count;
    !     }
    !     st->print_cr("Max failed chain length : %9llu", this->_debug_chain_failed_maximum_length);
    !     st->print_cr("Avg failed chain length : %9.3f", average);
    !   }
    !   st->print("-------------------------\n");
    !   {
    !     st->print_cr("Times table was resized : %9llu", this->_debug_resize_total_count);
    !     double average = 0.0;
    !     if (this->_debug_resize_total_count > 0) {
    !       average = (((double)this->_debug_resize_total_duration / (double)this->_debug_resize_total_count) + 0.5);
    !     }
    !     st->print_cr("Maximum resize time     : %9d ns (%.5f s)", (int)this->_debug_resize_max_duration, (double)this->_debug_resize_max_duration/1000000000.0);
    !     st->print_cr("Average resize time     : %9d ns (%.5f s)", (int)average, (double)average/1000000000.0);
    !     st->print_cr("Total resize time       : %9.5f s", (double)this->_debug_resize_total_duration/1000000000.0);
    !   }
    ! #endif
      }

      #ifndef PRODUCT

      template <class T, MEMFLAGS F> void Hashtable<T, F>::print() {
        ResourceMark rm;

    *** 323,347 ****
            entry = entry->next();
          }
        }
      }

    -
      template <MEMFLAGS F> void BasicHashtable<F>::verify() {
        int count = 0;
        for (int i = 0; i < table_size(); i++) {
          for (BasicHashtableEntry<F>* p = bucket(i); p != NULL; p = p->next()) {
            ++count;
          }
        }
        assert(count == number_of_entries(), "number of hashtable entries incorrect");
      }

    -
      #endif // PRODUCT

    -
      #ifdef ASSERT

      template <MEMFLAGS F> void BasicHashtable<F>::verify_lookup_length(double load) {
        if ((double)_lookup_length / (double)_lookup_count > load * 2.0) {
          warning("Performance bug: SystemDictionary lookup_count=%d "
    --- 612,633 ----
    *** 349,359 ****
                  _lookup_count, _lookup_length,
                  (double) _lookup_length / _lookup_count, load);
        }
      }

    ! #endif
      // Explicitly instantiate these types
      #if INCLUDE_ALL_GCS
      template class Hashtable<nmethod*, mtGC>;
      template class HashtableEntry<nmethod*, mtGC>;
      template class BasicHashtable<mtGC>;
    --- 635,646 ----
                  _lookup_count, _lookup_length,
                  (double) _lookup_length / _lookup_count, load);
        }
      }

    ! #endif // ASSERT
    !
      // Explicitly instantiate these types
      #if INCLUDE_ALL_GCS
      template class Hashtable<nmethod*, mtGC>;
      template class HashtableEntry<nmethod*, mtGC>;
      template class BasicHashtable<mtGC>;

src/share/vm/utilities/hashtable.cpp
Index Unified diffs Context diffs Sdiffs Wdiffs Patch New Old Previous File Next File