#306

Committed 30 Apr 2024 10:01PM UTC coverage: 97.645% (-0.5%) from 98.139%

Build # #306

Build Type

push

Committed by

Commit Message

Merge pull request #555 from apache/fix_pom_xml_header

Fix pom xml header

Run Details

26865 of 27513 relevant lines covered (97.64%)

0.98 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

98.23

/src/main/java/org/apache/datasketches/req/ReqCompactor.java

/*
 * 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.datasketches.req;

import static java.lang.Math.round;
import static org.apache.datasketches.common.Util.numberOfTrailingOnes;
import static org.apache.datasketches.req.BaseReqSketch.INIT_NUMBER_OF_SECTIONS;
import static org.apache.datasketches.req.ReqSketch.MIN_K;
import static org.apache.datasketches.req.ReqSketch.NOM_CAP_MULT;

import java.util.Random;

import org.apache.datasketches.memory.WritableBuffer;
import org.apache.datasketches.memory.WritableMemory;
import org.apache.datasketches.req.ReqSketch.CompactorReturn;

/**
 * The compactor class for the ReqSketch
 * @author Lee Rhodes
 */
class ReqCompactor {
  //finals
  private static final double SQRT2 = Math.sqrt(2.0);
  private final byte lgWeight;
  private final boolean hra;
  //state variables
  private long state; //State of the deterministic compaction schedule
  private float sectionSizeFlt;
  private int sectionSize; //initialized with k, minimum 4
  private byte numSections; //# of sections, initial size 3
  private boolean coin; //true or false at random for each compaction
  //objects
  private FloatBuffer buf;
  private final ReqDebug reqDebug = null;

  /**
   * Normal Constructor
   * @param lgWeight the lgWeight of this compactor
   * @param hra High Rank Accuracy
   * @param sectionSize initially the size of k
   * @param reqDebug The debug signaling interface
   */
  ReqCompactor(
      final byte lgWeight,
      final boolean hra,
      final int sectionSize,
      final ReqDebug reqDebug) {
    this.lgWeight = lgWeight;
    this.hra = hra;
    this.sectionSize = sectionSize;
    sectionSizeFlt = sectionSize;
    state = 0;
    coin = false;
    numSections = INIT_NUMBER_OF_SECTIONS;
    final int nomCap = getNomCapacity();
    buf = new FloatBuffer(2 * nomCap, nomCap, hra);
  }

  /**
   * Copy Constructor
   * @param other the compactor to be copied into this one
   */
  ReqCompactor(final ReqCompactor other) {
    lgWeight = other.lgWeight;
    hra = other.hra;
    sectionSizeFlt = other.sectionSizeFlt;
    numSections = other.numSections;
    sectionSize = other.sectionSize;
    state = other.state;
    coin = other.coin;
    buf = new FloatBuffer(other.buf);
  }

  /**
   * Construct from elements. The buffer will need to be constructed first
   */
  ReqCompactor(
      final byte lgWeight,
      final boolean hra,
      final long state,
      final float sectionSizeFlt,
      final byte numSections,
      final FloatBuffer buf) {
    this.lgWeight = lgWeight;
    this.hra = hra;
    this.buf = buf;
    this.sectionSizeFlt = sectionSizeFlt;
    this.numSections = numSections;
    this.state = state;
    coin = false;
    sectionSize = nearestEven(sectionSizeFlt);
    //ReqDebug left at null
  }

  /**
   * Perform a compaction operation on this compactor
   * @return the array of items to be promoted to the next level compactor
   */
  FloatBuffer compact(final CompactorReturn cReturn, final Random rand) {
    if (reqDebug != null) { reqDebug.emitCompactingStart(lgWeight); }
    final int startRetItems = buf.getCount();
    final int startNomCap = getNomCapacity();
    // choose a part of the buffer to compact
    final int secsToCompact = Math.min(numberOfTrailingOnes(state) + 1, numSections);
    final long compactionRange = computeCompactionRange(secsToCompact);
    final int compactionStart = (int) (compactionRange & 0xFFFF_FFFFL); //low 32
    final int compactionEnd = (int) (compactionRange >>> 32); //high 32
    assert compactionEnd - compactionStart >= 2;

    if ((state & 1L) == 1L) { coin = !coin; } //if numCompactions odd, flip coin;
    else { coin = rand.nextBoolean(); }       //random coin flip

    final FloatBuffer promote = buf.getEvensOrOdds(compactionStart, compactionEnd, coin);

    if (reqDebug != null) {
      reqDebug.emitCompactionDetail(compactionStart, compactionEnd, secsToCompact,
          promote.getCount(), coin);
    }

    buf.trimCount(buf.getCount() - (compactionEnd - compactionStart));
    state += 1;
    ensureEnoughSections();
    cReturn.deltaRetItems = buf.getCount() - startRetItems + promote.getCount();
    cReturn.deltaNomSize = getNomCapacity() - startNomCap;
    if (reqDebug != null) { reqDebug.emitCompactionDone(lgWeight); }
    return promote;
  } //End Compact

  /**
   * Gets a reference to this compactor's internal FloatBuffer
   * @return a reference to this compactor's internal FloatBuffer
   */
  FloatBuffer getBuffer() { return buf; }

  boolean getCoin() {
    return coin;
  }

  /**
   * Gets the lgWeight of this buffer
   * @return the lgWeight of this buffer
   */
  byte getLgWeight() {
    return lgWeight;
  }

  /**
   * Gets the current nominal capacity of this compactor.
   * @return the current nominal capacity of this compactor.
   */
  final int getNomCapacity() { //called from constructor
    return NOM_CAP_MULT * numSections * sectionSize;
  }

  /**
   * Serialize state(8) sectionSizeFlt(4), numSections(1), lgWeight(1), pad(2), count(4) + floatArr
   * @return required bytes to serialize.
   */
  int getSerializationBytes() {
    final int count = buf.getCount();
    return 8 + 4 + 1 + 1 + 2 + 4 + count * Float.BYTES; // 20 + array
  }

  int getNumSections() {
    return numSections;
  }

  int getSectionSize() {
    return sectionSize;
  }

  float getSectionSizeFlt() {
    return sectionSizeFlt;
  }

  long getState() {
    return state;
  }

  boolean isHighRankAccuracy() {
    return hra;
  }

  /**
   * Merge the other given compactor into this one. They both must have the
   * same lgWeight
   * @param other the other given compactor
   * @return this
   */
  ReqCompactor merge(final ReqCompactor other) {
    assert lgWeight == other.lgWeight;
    state |= other.state;
    while (ensureEnoughSections()) {}
    buf.sort();
    final FloatBuffer otherBuf = new FloatBuffer(other.buf);
    otherBuf.sort();
    if (otherBuf.getCount() > buf.getCount()) {
      otherBuf.mergeSortIn(buf);
      buf = otherBuf;
    } else {
      buf.mergeSortIn(otherBuf);
    }
    return this;
  }

  /**
   * Adjust the sectionSize and numSections if possible.
   * @return true if the SectionSize and NumSections were adjusted.
   */
  private boolean ensureEnoughSections() {
    final float szf;
    final int ne;
    if (state >= 1L << numSections - 1
        && sectionSize > MIN_K
        && (ne = nearestEven(szf = (float)(sectionSizeFlt / SQRT2))) >= MIN_K)
    {
      sectionSizeFlt = szf;
      sectionSize = ne;
      numSections <<= 1;
      buf.ensureCapacity(2 * getNomCapacity());
      if (reqDebug != null) { reqDebug.emitAdjSecSizeNumSec(lgWeight); }
      return true;
    }
    return false;
  }

  /**
   * Computes the start and end indices of the compacted region
   * @param secsToCompact the number of contiguous sections to compact
   * @return the  start and end indices of the compacted region
   */
  private long computeCompactionRange(final int secsToCompact) {
    final int bufLen = buf.getCount();
    int nonCompact = getNomCapacity() / 2 + (numSections - secsToCompact) * sectionSize;
    //make compacted region even:
    nonCompact = (bufLen - nonCompact & 1) == 1 ? nonCompact + 1 : nonCompact;
    final long low =  hra ? 0                   : nonCompact;
    final long high = hra ? bufLen - nonCompact : bufLen;
    return (high << 32) + low;
  }

  /**
   * Returns the nearest even integer to the given float. Also used by test.
   * @param fltVal the given float
   * @return the nearest even integer to the given float.
   */
  static final int nearestEven(final float fltVal) {
    return (int) round(fltVal / 2.0) << 1;
  }

  /**
   * ReqCompactor SERIALIZATION FORMAT.
   *
   * <p>Low significance bytes of this data structure are on the right just for visualization.
   * The multi-byte primitives are stored in native byte order.
   * The <i>byte</i> primitives are treated as unsigned. Multibyte primitives are indicated with "*" and
   * their size depends on the specific implementation.</p>
   *
   * <p>The binary format for a compactor: </p>
   *
   * <pre>
   * Binary Format. Starting offset is either 24 or 8, both are 8-byte aligned.
   *
   * +Long Adr / +Byte Offset
   *      ||    7   |    6   |    5   |    4   |    3   |    2   |    1   |    0   |
   *  0   ||-----------------------------state-------------------------------------|
   *
   *      ||   15   |   14   |   13   |   12   |   11   |   10   |    9   |    8   |
   *  1   ||----(empty)------|-#Sects-|--lgWt--|------------sectionSizeFlt---------|
   *
   *      ||        |        |        |        |        |        |        |   16   |
   *  2   ||--------------floats[]-------------|---------------count---------------|
   *
   * </pre>
   */
  byte[] toByteArray() {
    final int bytes = getSerializationBytes();
    final byte[] arr = new byte[bytes];
    final WritableBuffer wbuf = WritableMemory.writableWrap(arr).asWritableBuffer();
    wbuf.putLong(state);
    wbuf.putFloat(sectionSizeFlt);
    wbuf.putByte(lgWeight);
    wbuf.putByte(numSections);
    wbuf.incrementPosition(2); //pad 2
    //buf.sort(); //sort if necessary
    wbuf.putInt(buf.getCount()); //count
    wbuf.putByteArray(buf.floatsToBytes(), 0, Float.BYTES * buf.getCount());
    assert wbuf.getPosition() == bytes;
    return arr;
  }

  /**
   * Returns a printable formatted prefix string summarizing the list.
   * The first number is the compactor height. the second number in brackets is the current count
   * of the compactor buffer. The third number in brackets is the nominal capacity of the compactor.
   * @return a printable formatted prefix string summarizing the list.
   */
  String toListPrefix() {
    final int h = getLgWeight();
    final int len = buf.getCount();
    final int nom = getNomCapacity();
    final int secSz = getSectionSize();
    final int numSec = getNumSections();
    final long num = getState();
    final String prefix = String.format(
      "  C:%d Len:%d NomSz:%d SecSz:%d NumSec:%d State:%d",
           h, len, nom, secSz, numSec, num);
    return prefix;
  }

}

1	/*
2	* Licensed to the Apache Software Foundation (ASF) under one
3	* or more contributor license agreements. See the NOTICE file
4	* distributed with this work for additional information
5	* regarding copyright ownership. The ASF licenses this file
6	* to you under the Apache License, Version 2.0 (the
7	* "License"); you may not use this file except in compliance
8	* with the License. You may obtain a copy of the License at
9	*
10	* http://www.apache.org/licenses/LICENSE-2.0
11	*
12	* Unless required by applicable law or agreed to in writing,
13	* software distributed under the License is distributed on an
14	* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15	* KIND, either express or implied. See the License for the
16	* specific language governing permissions and limitations
17	* under the License.
18	*/
19
20	package org.apache.datasketches.req;
21
22	import static java.lang.Math.round;
23	import static org.apache.datasketches.common.Util.numberOfTrailingOnes;
24	import static org.apache.datasketches.req.BaseReqSketch.INIT_NUMBER_OF_SECTIONS;
25	import static org.apache.datasketches.req.ReqSketch.MIN_K;
26	import static org.apache.datasketches.req.ReqSketch.NOM_CAP_MULT;
27
28	import java.util.Random;
29
30	import org.apache.datasketches.memory.WritableBuffer;
31	import org.apache.datasketches.memory.WritableMemory;
32	import org.apache.datasketches.req.ReqSketch.CompactorReturn;
33
34	/**
35	* The compactor class for the ReqSketch
36	* @author Lee Rhodes
37	*/
38	class ReqCompactor {
39	//finals
40	private static final double SQRT2 = Math.sqrt(2.0);	1✔
41	private final byte lgWeight;
42	private final boolean hra;
43	//state variables
44	private long state; //State of the deterministic compaction schedule
45	private float sectionSizeFlt;
46	private int sectionSize; //initialized with k, minimum 4
47	private byte numSections; //# of sections, initial size 3
48	private boolean coin; //true or false at random for each compaction
49	//objects
50	private FloatBuffer buf;
51	private final ReqDebug reqDebug = null;	1✔
52
53	/**
54	* Normal Constructor
55	* @param lgWeight the lgWeight of this compactor
56	* @param hra High Rank Accuracy
57	* @param sectionSize initially the size of k
58	* @param reqDebug The debug signaling interface
59	*/
60	ReqCompactor(
61	final byte lgWeight,
62	final boolean hra,
63	final int sectionSize,
64	final ReqDebug reqDebug) {	1✔
65	this.lgWeight = lgWeight;	1✔
66	this.hra = hra;	1✔
67	this.sectionSize = sectionSize;	1✔
68	sectionSizeFlt = sectionSize;	1✔
69	state = 0;	1✔
70	coin = false;	1✔
71	numSections = INIT_NUMBER_OF_SECTIONS;	1✔
72	final int nomCap = getNomCapacity();	1✔
73	buf = new FloatBuffer(2 * nomCap, nomCap, hra);	1✔
74	}	1✔
75
76	/**
77	* Copy Constructor
78	* @param other the compactor to be copied into this one
79	*/
80	ReqCompactor(final ReqCompactor other) {	1✔
81	lgWeight = other.lgWeight;	1✔
82	hra = other.hra;	1✔
83	sectionSizeFlt = other.sectionSizeFlt;	1✔
84	numSections = other.numSections;	1✔
85	sectionSize = other.sectionSize;	1✔
86	state = other.state;	1✔
87	coin = other.coin;	1✔
88	buf = new FloatBuffer(other.buf);	1✔
89	}	1✔
90
91	/**
92	* Construct from elements. The buffer will need to be constructed first
93	*/
94	ReqCompactor(
95	final byte lgWeight,
96	final boolean hra,
97	final long state,
98	final float sectionSizeFlt,
99	final byte numSections,
100	final FloatBuffer buf) {	1✔
101	this.lgWeight = lgWeight;	1✔
102	this.hra = hra;	1✔
103	this.buf = buf;	1✔
104	this.sectionSizeFlt = sectionSizeFlt;	1✔
105	this.numSections = numSections;	1✔
106	this.state = state;	1✔
107	coin = false;	1✔
108	sectionSize = nearestEven(sectionSizeFlt);	1✔
109	//ReqDebug left at null
110	}	1✔
111
112	/**
113	* Perform a compaction operation on this compactor
114	* @return the array of items to be promoted to the next level compactor
115	*/
116	FloatBuffer compact(final CompactorReturn cReturn, final Random rand) {
117	if (reqDebug != null) { reqDebug.emitCompactingStart(lgWeight); }	1✔
118	final int startRetItems = buf.getCount();	1✔
119	final int startNomCap = getNomCapacity();	1✔
120	// choose a part of the buffer to compact
121	final int secsToCompact = Math.min(numberOfTrailingOnes(state) + 1, numSections);	1✔
122	final long compactionRange = computeCompactionRange(secsToCompact);	1✔
123	final int compactionStart = (int) (compactionRange & 0xFFFF_FFFFL); //low 32	1✔
124	final int compactionEnd = (int) (compactionRange >>> 32); //high 32	1✔
125	assert compactionEnd - compactionStart >= 2;	1✔
126
127	if ((state & 1L) == 1L) { coin = !coin; } //if numCompactions odd, flip coin;	1✔
128	else { coin = rand.nextBoolean(); } //random coin flip	1✔
129
130	final FloatBuffer promote = buf.getEvensOrOdds(compactionStart, compactionEnd, coin);	1✔
131
132	if (reqDebug != null) {	1✔
133	reqDebug.emitCompactionDetail(compactionStart, compactionEnd, secsToCompact,	×
134	promote.getCount(), coin);	×
135	}
136
137	buf.trimCount(buf.getCount() - (compactionEnd - compactionStart));	1✔
138	state += 1;	1✔
139	ensureEnoughSections();	1✔
140	cReturn.deltaRetItems = buf.getCount() - startRetItems + promote.getCount();	1✔
141	cReturn.deltaNomSize = getNomCapacity() - startNomCap;	1✔
142	if (reqDebug != null) { reqDebug.emitCompactionDone(lgWeight); }	1✔
143	return promote;	1✔
144	} //End Compact
145
146	/**
147	* Gets a reference to this compactor's internal FloatBuffer
148	* @return a reference to this compactor's internal FloatBuffer
149	*/
150	FloatBuffer getBuffer() { return buf; }	1✔
151
152	boolean getCoin() {
153	return coin;	1✔
154	}
155
156	/**
157	* Gets the lgWeight of this buffer
158	* @return the lgWeight of this buffer
159	*/
160	byte getLgWeight() {
161	return lgWeight;	1✔
162	}
163
164	/**
165	* Gets the current nominal capacity of this compactor.
166	* @return the current nominal capacity of this compactor.
167	*/
168	final int getNomCapacity() { //called from constructor
169	return NOM_CAP_MULT * numSections * sectionSize;	1✔
170	}
171
172	/**
173	* Serialize state(8) sectionSizeFlt(4), numSections(1), lgWeight(1), pad(2), count(4) + floatArr
174	* @return required bytes to serialize.
175	*/
176	int getSerializationBytes() {
177	final int count = buf.getCount();	1✔
178	return 8 + 4 + 1 + 1 + 2 + 4 + count * Float.BYTES; // 20 + array	1✔
179	}
180
181	int getNumSections() {
182	return numSections;	1✔
183	}
184
185	int getSectionSize() {
186	return sectionSize;	1✔
187	}
188
189	float getSectionSizeFlt() {
190	return sectionSizeFlt;	1✔
191	}
192
193	long getState() {
194	return state;	1✔
195	}
196
197	boolean isHighRankAccuracy() {
198	return hra;	1✔
199	}
200
201	/**
202	* Merge the other given compactor into this one. They both must have the
203	* same lgWeight
204	* @param other the other given compactor
205	* @return this
206	*/
207	ReqCompactor merge(final ReqCompactor other) {
208	assert lgWeight == other.lgWeight;	1✔
209	state \|= other.state;	1✔
210	while (ensureEnoughSections()) {}	1✔
211	buf.sort();	1✔
212	final FloatBuffer otherBuf = new FloatBuffer(other.buf);	1✔
213	otherBuf.sort();	1✔
214	if (otherBuf.getCount() > buf.getCount()) {	1✔
215	otherBuf.mergeSortIn(buf);	1✔
216	buf = otherBuf;	1✔
217	} else {
218	buf.mergeSortIn(otherBuf);	1✔
219	}
220	return this;	1✔
221	}
222
223	/**
224	* Adjust the sectionSize and numSections if possible.
225	* @return true if the SectionSize and NumSections were adjusted.
226	*/
227	private boolean ensureEnoughSections() {
228	final float szf;
229	final int ne;
230	if (state >= 1L << numSections - 1	1✔
231	&& sectionSize > MIN_K
232	&& (ne = nearestEven(szf = (float)(sectionSizeFlt / SQRT2))) >= MIN_K)	1✔
233	{
234	sectionSizeFlt = szf;	1✔
235	sectionSize = ne;	1✔
236	numSections <<= 1;	1✔
237	buf.ensureCapacity(2 * getNomCapacity());	1✔
238	if (reqDebug != null) { reqDebug.emitAdjSecSizeNumSec(lgWeight); }	1✔
239	return true;	1✔
240	}
241	return false;	1✔
242	}
243
244	/**
245	* Computes the start and end indices of the compacted region
246	* @param secsToCompact the number of contiguous sections to compact
247	* @return the start and end indices of the compacted region
248	*/
249	private long computeCompactionRange(final int secsToCompact) {
250	final int bufLen = buf.getCount();	1✔
251	int nonCompact = getNomCapacity() / 2 + (numSections - secsToCompact) * sectionSize;	1✔
252	//make compacted region even:
253	nonCompact = (bufLen - nonCompact & 1) == 1 ? nonCompact + 1 : nonCompact;	1✔
254	final long low = hra ? 0 : nonCompact;	1✔
255	final long high = hra ? bufLen - nonCompact : bufLen;	1✔
256	return (high << 32) + low;	1✔
257	}
258
259	/**
260	* Returns the nearest even integer to the given float. Also used by test.
261	* @param fltVal the given float
262	* @return the nearest even integer to the given float.
263	*/
264	static final int nearestEven(final float fltVal) {
265	return (int) round(fltVal / 2.0) << 1;	1✔
266	}
267
268	/**
269	* ReqCompactor SERIALIZATION FORMAT.
270	*
271	* <p>Low significance bytes of this data structure are on the right just for visualization.
272	* The multi-byte primitives are stored in native byte order.
273	* The <i>byte</i> primitives are treated as unsigned. Multibyte primitives are indicated with "*" and
274	* their size depends on the specific implementation.</p>
275	*
276	* <p>The binary format for a compactor: </p>
277	*
278	* <pre>
279	* Binary Format. Starting offset is either 24 or 8, both are 8-byte aligned.
280	*
281	* +Long Adr / +Byte Offset
282	* \|\| 7 \| 6 \| 5 \| 4 \| 3 \| 2 \| 1 \| 0 \|
283	* 0 \|\|-----------------------------state-------------------------------------\|
284	*
285	* \|\| 15 \| 14 \| 13 \| 12 \| 11 \| 10 \| 9 \| 8 \|
286	* 1 \|\|----(empty)------\|-#Sects-\|--lgWt--\|------------sectionSizeFlt---------\|
287	*
288	* \|\| \| \| \| \| \| \| \| 16 \|
289	* 2 \|\|--------------floats[]-------------\|---------------count---------------\|
290	*
291	* </pre>
292	*/
293	byte[] toByteArray() {
294	final int bytes = getSerializationBytes();	1✔
295	final byte[] arr = new byte[bytes];	1✔
296	final WritableBuffer wbuf = WritableMemory.writableWrap(arr).asWritableBuffer();	1✔
297	wbuf.putLong(state);	1✔
298	wbuf.putFloat(sectionSizeFlt);	1✔
299	wbuf.putByte(lgWeight);	1✔
300	wbuf.putByte(numSections);	1✔
301	wbuf.incrementPosition(2); //pad 2	1✔
302	//buf.sort(); //sort if necessary
303	wbuf.putInt(buf.getCount()); //count	1✔
304	wbuf.putByteArray(buf.floatsToBytes(), 0, Float.BYTES * buf.getCount());	1✔
305	assert wbuf.getPosition() == bytes;	1✔
306	return arr;	1✔
307	}
308
309	/**
310	* Returns a printable formatted prefix string summarizing the list.
311	* The first number is the compactor height. the second number in brackets is the current count
312	* of the compactor buffer. The third number in brackets is the nominal capacity of the compactor.
313	* @return a printable formatted prefix string summarizing the list.
314	*/
315	String toListPrefix() {
316	final int h = getLgWeight();	1✔
317	final int len = buf.getCount();	1✔
318	final int nom = getNomCapacity();	1✔
319	final int secSz = getSectionSize();	1✔
320	final int numSec = getNumSections();	1✔
321	final long num = getState();	1✔
322	final String prefix = String.format(	1✔
323	" C:%d Len:%d NomSz:%d SecSz:%d NumSec:%d State:%d",
324	h, len, nom, secSz, numSec, num);	1✔
325	return prefix;	1✔
326	}
327
328	}

apache / datasketches-java / #306

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous