<commit_before>/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 * 
 *   http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */

package org.apache.uima.jcas.impl;


import java.util.Arrays;
import java.util.function.IntFunction;

import org.apache.uima.internal.util.Misc;
import org.apache.uima.jcas.cas.TOP;

/**
 * Part of the JCasHashMap.
 * There are multiple instances of this class, one per concurrancy level
 */
class JCasHashMapSubMap {
  
  // set to true to collect statistics for tuning
  // you have to also put a call to jcas.showJfsFromCaddrHistogram() at the end of the run
  private static final boolean TUNE = JCasHashMap.TUNE;

  // info kept per probe:  the address, and the current "delta"
  //   the delta is the one to use to go to the next "probe" address
  //   it starts at 1, and goes up by 1 to 23 (a prime)
  // These are kept in thread local constants, one per thread.
  private static final int PROBE_ADDR_INDEX = 0;
  private static final int PROBE_DELTA_INDEX = 1;

  
  static final ThreadLocal<int[]> probeInfoGet = new ThreadLocal<int[]>() {
    protected int[] initialValue() { return new int[2]; } };
      
  static final ThreadLocal<int[]> probeInfoPutInner = new ThreadLocal<int[]>() {
    protected int[] initialValue() { return new int[2]; } };

  //These are for tuning measurements
  int histogram [];
  int maxProbe = 0;
  int maxProbeAfterContinue = 0;
  int continues = 0;;

  /**
   * This lock is sometimes held by put, putIfAbsent, get, clear
   *   - not held if putIfAbsent or get find existing (non-reserve) item
   *     -- assumes no "remove" operation
   */
  private final Object synclock = new Object();
  
  private int sizeWhichTriggersExpansion;
  int size; // number of elements in the table 
  
  volatile TOP [] table;
  private boolean secondTimeShrinkable = false;
  
  private final float loadFactor;
  private final int subMapInitialCapacity;
  private final int concurrencyLevelBits;
  
  JCasHashMapSubMap(float loadFactor, int subMapInitialCapacity, int concurrencyLevelBits) {
    this.loadFactor = loadFactor;
    this.subMapInitialCapacity = subMapInitialCapacity;
    this.concurrencyLevelBits = concurrencyLevelBits;
    newTable(subMapInitialCapacity);
  }
  
  private JCasHashMapSubMap newTable(int capacity) {
    table = newTableKeepSize(capacity);
    size = 0;
    if (TUNE) {
      histogram = new int[200];
      Arrays.fill(histogram, 0);
    }
    return this;
  }
  
  private TOP[] newTableKeepSize(int capacity) {
    assert(Integer.bitCount(capacity) == 1);
    TOP[] t = new TOP[capacity];
    sizeWhichTriggersExpansion = (int)(capacity * loadFactor);
    return t;
  }
  
  private void incrementSize() {
//    synchronized(synclock) {  // guaranteed by caller
  //    assert(lock.getHoldCount() > 0);
      if (size >= sizeWhichTriggersExpansion) {
        increaseTableCapacity();
      }
      size++;
//    }
  }
  
  // Does size management - shrinking overly large tables after the 2nd time
  void clear() {
    synchronized(synclock) {
      // see if size is less than the 1/2 size that triggers expansion
      if (size <  (sizeWhichTriggersExpansion >>> 1)) {
        // if 2nd time then shrink by 50%
        //   this is done to avoid thrashing around the threshold
        if (secondTimeShrinkable) {
          secondTimeShrinkable = false;
          final int newCapacity = Math.max(subMapInitialCapacity, table.length >>> 1);
          if (newCapacity < table.length) { 
            newTable(newCapacity);  // shrink table by 50%
          } else { // don't shrink below minimum
            Arrays.fill(table,  null);
          }
          size = 0;
          return;
        } else {
          secondTimeShrinkable = true;
        }
      } else {
        secondTimeShrinkable = false; // reset this to require 2 triggers in a row
      }
      size = 0;
      Arrays.fill(table, null);
    } 
  }      
   
  /**
   * find a real item or a reserve item, matching the key
   * Can be called under lock or not.
   * Using a ref to the current value of table, searches that int array.
   *   If, during the search, the table is resized, it continues using the
   *   ** before the resize ** int array referenced by localTable 
   *     The answer will only be OK if the key is found for a real value.  
   *     Results that yield null or Reserved slots must be re-searched, 
   *     under a lock (caller needs to do this).
   * @param key -
   * @param hash -
   * @param probeInfo - used to get/receive multiple int values;
   *    0: (in/out) startProbe or -1; -1 starts at the hash & bitMask
   *    1: (in/out) probeDelta (starts at 1)
   * @return the probeAddr in original table (which might have been resized)
   */
  private TOP find(final TOP[] localTable, final int key, final int hash, final int[] probeInfo) {
    int nbrProbes = 1;  // for histogram
    final int localTblLength = localTable.length;
    final int bitMask = localTblLength - 1;

    final int startProbe = probeInfo[PROBE_ADDR_INDEX];
    final boolean isInitialProbe = startProbe == -1;
    final boolean isContinue = TUNE && !isInitialProbe; 
    int probeAddr = isInitialProbe ? (hash & bitMask) : startProbe;
    
    int probeDelta = probeInfo[PROBE_DELTA_INDEX];
    //debug
    if (probeDelta <= 0) {
      System.out.println("debug");
    }
    assert probeDelta > 0;
    
    // Next modification is overall, slower (very slightly)
    
//    int initialAdj = 0; 
//    if (probeDelta == 1) {
//      // This is an attempt to reduce collision chain clustering for things that hash to
//      //   the same spot, by slightly varying the starting delta
//      // xxxx xxxx  xxxx xxxx   xxxx xxxx  xxxx xxxx
//      //    x xxxx  xxxx xxxx   xxxx xxxx  xxxx xxxx    zzz after >>> concurrencyLevelBits eg 3
//      //    | ||  3 bits for randomizing
//      final int shiftAmt = 32 - concurrencyLevelBits   // number of significant bits
//                       - 3;  // 3 gives low order 3 bits, a number from 0 to 7
//      initialAdj = (hash >>> shiftAmt);
//    }
    
    TOP m = localTable[probeAddr];  // first probe doesn't add delta, facilitates restarting after acquiring lock

    while (true) {
      if (m == null) {
        // not in table
        setProbeInfo(probeInfo, probeAddr, probeDelta);  
        return null;  
      }
      
      if (m._id() == key) {
        setProbeInfo(probeInfo, probeAddr, probeDelta);<commit_msg>no Jira, comment out some debug code<commit_after>/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 * 
 *   http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */

package org.apache.uima.jcas.impl;


import java.util.Arrays;
import java.util.function.IntFunction;

import org.apache.uima.internal.util.Misc;
import org.apache.uima.jcas.cas.TOP;

/**
 * Part of the JCasHashMap.
 * There are multiple instances of this class, one per concurrancy level
 */
class JCasHashMapSubMap {
  
  // set to true to collect statistics for tuning
  // you have to also put a call to jcas.showJfsFromCaddrHistogram() at the end of the run
  private static final boolean TUNE = JCasHashMap.TUNE;

  // info kept per probe:  the address, and the current "delta"
  //   the delta is the one to use to go to the next "probe" address
  //   it starts at 1, and goes up by 1 to 23 (a prime)
  // These are kept in thread local constants, one per thread.
  private static final int PROBE_ADDR_INDEX = 0;
  private static final int PROBE_DELTA_INDEX = 1;

  
  static final ThreadLocal<int[]> probeInfoGet = new ThreadLocal<int[]>() {
    protected int[] initialValue() { return new int[2]; } };
      
  static final ThreadLocal<int[]> probeInfoPutInner = new ThreadLocal<int[]>() {
    protected int[] initialValue() { return new int[2]; } };

  //These are for tuning measurements
  int histogram [];
  int maxProbe = 0;
  int maxProbeAfterContinue = 0;
  int continues = 0;;

  /**
   * This lock is sometimes held by put, putIfAbsent, get, clear
   *   - not held if putIfAbsent or get find existing (non-reserve) item
   *     -- assumes no "remove" operation
   */
  private final Object synclock = new Object();
  
  private int sizeWhichTriggersExpansion;
  int size; // number of elements in the table 
  
  volatile TOP [] table;
  private boolean secondTimeShrinkable = false;
  
  private final float loadFactor;
  private final int subMapInitialCapacity;
  private final int concurrencyLevelBits;
  
  JCasHashMapSubMap(float loadFactor, int subMapInitialCapacity, int concurrencyLevelBits) {
    this.loadFactor = loadFactor;
    this.subMapInitialCapacity = subMapInitialCapacity;
    this.concurrencyLevelBits = concurrencyLevelBits;
    newTable(subMapInitialCapacity);
  }
  
  private JCasHashMapSubMap newTable(int capacity) {
    table = newTableKeepSize(capacity);
    size = 0;
    if (TUNE) {
      histogram = new int[200];
      Arrays.fill(histogram, 0);
    }
    return this;
  }
  
  private TOP[] newTableKeepSize(int capacity) {
    assert(Integer.bitCount(capacity) == 1);
    TOP[] t = new TOP[capacity];
    sizeWhichTriggersExpansion = (int)(capacity * loadFactor);
    return t;
  }
  
  private void incrementSize() {
//    synchronized(synclock) {  // guaranteed by caller
  //    assert(lock.getHoldCount() > 0);
      if (size >= sizeWhichTriggersExpansion) {
        increaseTableCapacity();
      }
      size++;
//    }
  }
  
  // Does size management - shrinking overly large tables after the 2nd time
  void clear() {
    synchronized(synclock) {
      // see if size is less than the 1/2 size that triggers expansion
      if (size <  (sizeWhichTriggersExpansion >>> 1)) {
        // if 2nd time then shrink by 50%
        //   this is done to avoid thrashing around the threshold
        if (secondTimeShrinkable) {
          secondTimeShrinkable = false;
          final int newCapacity = Math.max(subMapInitialCapacity, table.length >>> 1);
          if (newCapacity < table.length) { 
            newTable(newCapacity);  // shrink table by 50%
          } else { // don't shrink below minimum
            Arrays.fill(table,  null);
          }
          size = 0;
          return;
        } else {
          secondTimeShrinkable = true;
        }
      } else {
        secondTimeShrinkable = false; // reset this to require 2 triggers in a row
      }
      size = 0;
      Arrays.fill(table, null);
    } 
  }      
   
  /**
   * find a real item or a reserve item, matching the key
   * Can be called under lock or not.
   * Using a ref to the current value of table, searches that int array.
   *   If, during the search, the table is resized, it continues using the
   *   ** before the resize ** int array referenced by localTable 
   *     The answer will only be OK if the key is found for a real value.  
   *     Results that yield null or Reserved slots must be re-searched, 
   *     under a lock (caller needs to do this).
   * @param key -
   * @param hash -
   * @param probeInfo - used to get/receive multiple int values;
   *    0: (in/out) startProbe or -1; -1 starts at the hash & bitMask
   *    1: (in/out) probeDelta (starts at 1)
   * @return the probeAddr in original table (which might have been resized)
   */
  private TOP find(final TOP[] localTable, final int key, final int hash, final int[] probeInfo) {
    int nbrProbes = 1;  // for histogram
    final int localTblLength = localTable.length;
    final int bitMask = localTblLength - 1;

    final int startProbe = probeInfo[PROBE_ADDR_INDEX];
    final boolean isInitialProbe = startProbe == -1;
    final boolean isContinue = TUNE && !isInitialProbe; 
    int probeAddr = isInitialProbe ? (hash & bitMask) : startProbe;
    
    int probeDelta = probeInfo[PROBE_DELTA_INDEX];
    //debug
//    if (probeDelta <= 0) {
//      System.out.println("debug");
//    }
    assert probeDelta > 0;
    
    // Next modification is overall, slower (very slightly)
    
//    int initialAdj = 0; 
//    if (probeDelta == 1) {
//      // This is an attempt to reduce collision chain clustering for things that hash to
//      //   the same spot, by slightly varying the starting delta
//      // xxxx xxxx  xxxx xxxx   xxxx xxxx  xxxx xxxx
//      //    x xxxx  xxxx xxxx   xxxx xxxx  xxxx xxxx    zzz after >>> concurrencyLevelBits eg 3
//      //    | ||  3 bits for randomizing
//      final int shiftAmt = 32 - concurrencyLevelBits   // number of significant bits
//                       - 3;  // 3 gives low order 3 bits, a number from 0 to 7
//      initialAdj = (hash >>> shiftAmt);
//    }
    
    TOP m = localTable[probeAddr];  // first probe doesn't add delta, facilitates restarting after acquiring lock

    while (true) {
      if (m == null) {
        // not in table
        setProbeInfo(probeInfo, probeAddr, probeDelta);  
        return null;  
      }
      
      if (m._id() == key) {
        setProbeInfo(probeInfo, probeAddr, probeDelta);
{'fraction_non_alphanumeric': 0.08883763192842664, 'fraction_numerical': 0.007828335779688264, 'mean_word_length': 2.6397863139150344, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 41, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2406700', 'n_tokens_mistral': 4292, 'n_tokens_neox': 4105, 'n_words': 1567}