Repository: lucy
Updated Branches:
refs/heads/master d657bd167 -> 94c6aa2ea
Improve integer division with rounded-up result
There's no need for floating point math:
ceil((double)p / (double)q) == (p + q - 1) / q
(ignoring overflow)
Project: http://git-wip-us.apache.org/repos/asf/lucy/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucy/commit/04bd80fe
Tree: http://git-wip-us.apache.org/repos/asf/lucy/tree/04bd80fe
Diff: http://git-wip-us.apache.org/repos/asf/lucy/diff/04bd80fe
Branch: refs/heads/master
Commit: 04bd80fe37340838015ec6a61293fb6865fa9fbe
Parents: d657bd1
Author: Nick Wellnhofer <[email protected]>
Authored: Sun Mar 20 23:13:32 2016 +0100
Committer: Nick Wellnhofer <[email protected]>
Committed: Sun Mar 20 23:13:32 2016 +0100
----------------------------------------------------------------------
core/Lucy/Index/DeletionsWriter.c | 5 +---
core/Lucy/Index/SortFieldWriter.c | 33 ++++++++++++++++++++------
core/Lucy/Object/BitVector.c | 32 ++++++++++++-------------
core/Lucy/Test/Search/TestSeriesMatcher.c | 3 +--
4 files changed, 43 insertions(+), 30 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucy/blob/04bd80fe/core/Lucy/Index/DeletionsWriter.c
----------------------------------------------------------------------
diff --git a/core/Lucy/Index/DeletionsWriter.c
b/core/Lucy/Index/DeletionsWriter.c
index 103feae..ec36fbf 100644
--- a/core/Lucy/Index/DeletionsWriter.c
+++ b/core/Lucy/Index/DeletionsWriter.c
@@ -18,8 +18,6 @@
#define C_LUCY_DEFAULTDELETIONSWRITER
#include "Lucy/Util/ToolSet.h"
-#include <math.h>
-
#include "Clownfish/HashIterator.h"
#include "Clownfish/Num.h"
#include "Lucy/Index/DeletionsWriter.h"
@@ -151,8 +149,7 @@ DefDelWriter_Finish_IMP(DefaultDeletionsWriter *self) {
if (ivars->updated[i]) {
BitVector *deldocs = (BitVector*)Vec_Fetch(ivars->bit_vecs, i);
int32_t doc_max = SegReader_Doc_Max(seg_reader);
- double used = (doc_max + 1) / 8.0;
- uint32_t byte_size = (uint32_t)ceil(used);
+ uint32_t byte_size = (((uint32_t)doc_max + 1) + 7) / 8;
uint32_t new_max = byte_size * 8 - 1;
String *filename = S_del_filename(self, seg_reader);
OutStream *outstream = Folder_Open_Out(folder, filename);
http://git-wip-us.apache.org/repos/asf/lucy/blob/04bd80fe/core/Lucy/Index/SortFieldWriter.c
----------------------------------------------------------------------
diff --git a/core/Lucy/Index/SortFieldWriter.c
b/core/Lucy/Index/SortFieldWriter.c
index f761014..93c690b 100644
--- a/core/Lucy/Index/SortFieldWriter.c
+++ b/core/Lucy/Index/SortFieldWriter.c
@@ -17,7 +17,6 @@
#define C_LUCY_SORTFIELDWRITER
#define C_LUCY_SFWRITERELEM
#include "Lucy/Util/ToolSet.h"
-#include <math.h>
#include "Lucy/Index/SortFieldWriter.h"
#include "Lucy/Index/Inverter.h"
@@ -603,16 +602,36 @@ S_write_files(SortFieldWriter *self, OutStream *ord_out,
OutStream *ix_out,
int32_t ord_width = ivars->ord_width;
// Write ords.
- const double BITS_PER_BYTE = 8.0;
- double bytes_per_doc = ord_width / BITS_PER_BYTE;
- double byte_count = ceil((doc_max + 1) * bytes_per_doc);
- char *compressed_ords
- = (char*)CALLOCATE((size_t)byte_count, sizeof(char));
+ size_t byte_count;
+ switch (ord_width) {
+ case 1:
+ byte_count = (((size_t)doc_max + 1) + 7) / 8;
+ break;
+ case 2:
+ byte_count = (((size_t)doc_max + 1) + 3) / 4;
+ break;
+ case 4:
+ byte_count = (((size_t)doc_max + 1) + 1) / 2;
+ break;
+ case 8:
+ byte_count = (size_t)doc_max + 1;
+ break;
+ case 16:
+ byte_count = ((size_t)doc_max + 1) * 2;
+ break;
+ case 32:
+ byte_count = ((size_t)doc_max + 1) * 4;
+ break;
+ default:
+ THROW(ERR, "Invalid width: %i32", ord_width);
+
+ }
+ char *compressed_ords = (char*)CALLOCATE(byte_count, sizeof(char));
for (int32_t i = 0; i <= doc_max; i++) {
int32_t real_ord = ords[i] == -1 ? null_ord : ords[i];
S_write_ord(compressed_ords, ord_width, i, real_ord);
}
- OutStream_Write_Bytes(ord_out, compressed_ords, (size_t)byte_count);
+ OutStream_Write_Bytes(ord_out, compressed_ords, byte_count);
FREEMEM(compressed_ords);
FREEMEM(ords);
http://git-wip-us.apache.org/repos/asf/lucy/blob/04bd80fe/core/Lucy/Object/BitVector.c
----------------------------------------------------------------------
diff --git a/core/Lucy/Object/BitVector.c b/core/Lucy/Object/BitVector.c
index b73e762..d6406f2 100644
--- a/core/Lucy/Object/BitVector.c
+++ b/core/Lucy/Object/BitVector.c
@@ -17,8 +17,6 @@
#define C_LUCY_BITVECTOR
#include "Lucy/Util/ToolSet.h"
-#include <math.h>
-
#include "Lucy/Object/BitVector.h"
#include "Lucy/Util/NumberUtils.h"
@@ -58,7 +56,7 @@ BitVec_new(uint32_t capacity) {
BitVector*
BitVec_init(BitVector *self, uint32_t capacity) {
BitVectorIVARS *const ivars = BitVec_IVARS(self);
- const uint32_t byte_size = (uint32_t)ceil(capacity / 8.0);
+ const uint32_t byte_size = (capacity + 7) / 8;
// Derive.
ivars->bits = capacity
@@ -82,7 +80,7 @@ BitVector*
BitVec_Clone_IMP(BitVector *self) {
BitVectorIVARS *const ivars = BitVec_IVARS(self);
BitVector *other = BitVec_new(ivars->cap);
- uint32_t byte_size = (uint32_t)ceil(ivars->cap / 8.0);
+ uint32_t byte_size = (ivars->cap + 7) / 8;
BitVectorIVARS *const ovars = BitVec_IVARS(other);
// Forbid inheritance.
@@ -111,8 +109,8 @@ BitVec_Mimic_IMP(BitVector *self, Obj *other) {
CERTIFY(other, BITVECTOR);
BitVectorIVARS *const ivars = BitVec_IVARS(self);
BitVectorIVARS *const ovars = BitVec_IVARS((BitVector*)other);
- const uint32_t my_byte_size = (uint32_t)ceil(ivars->cap / 8.0);
- const uint32_t other_byte_size = (uint32_t)ceil(ovars->cap / 8.0);
+ const uint32_t my_byte_size = (ivars->cap + 7) / 8;
+ const uint32_t other_byte_size = (ovars->cap + 7) / 8;
if (my_byte_size > other_byte_size) {
uint32_t space = my_byte_size - other_byte_size;
memset(ivars->bits + other_byte_size, 0, space);
@@ -127,8 +125,8 @@ void
BitVec_Grow_IMP(BitVector *self, uint32_t capacity) {
BitVectorIVARS *const ivars = BitVec_IVARS(self);
if (capacity > ivars->cap) {
- const size_t old_byte_cap = (size_t)ceil(ivars->cap / 8.0);
- const size_t new_byte_cap = (size_t)ceil((capacity + 1) / 8.0);
+ const size_t old_byte_cap = (ivars->cap + 7) / 8;
+ const size_t new_byte_cap = (capacity + 7) / 8;
const size_t num_new_bytes = new_byte_cap - old_byte_cap;
ivars->bits = (uint8_t*)REALLOCATE(ivars->bits, new_byte_cap);
@@ -159,7 +157,7 @@ BitVec_Clear_IMP(BitVector *self, uint32_t tick) {
void
BitVec_Clear_All_IMP(BitVector *self) {
BitVectorIVARS *const ivars = BitVec_IVARS(self);
- const size_t byte_size = (size_t)ceil(ivars->cap / 8.0);
+ const size_t byte_size = (ivars->cap + 7) / 8;
memset(ivars->bits, 0, byte_size);
}
@@ -184,7 +182,7 @@ S_first_bit_in_nonzero_byte(uint8_t num) {
int32_t
BitVec_Next_Hit_IMP(BitVector *self, uint32_t tick) {
BitVectorIVARS *const ivars = BitVec_IVARS(self);
- size_t byte_size = (size_t)ceil(ivars->cap / 8.0);
+ size_t byte_size = (ivars->cap + 7) / 8;
uint8_t *const limit = ivars->bits + byte_size;
uint8_t *ptr = ivars->bits + (tick >> 3);
@@ -224,7 +222,7 @@ BitVec_And_IMP(BitVector *self, const BitVector *other) {
const uint32_t min_cap = ivars->cap < ovars->cap
? ivars->cap
: ovars->cap;
- const size_t byte_size = (size_t)ceil(min_cap / 8.0);
+ const size_t byte_size = (min_cap + 7) / 8;
uint8_t *const limit = bits_a + byte_size;
// Intersection.
@@ -235,7 +233,7 @@ BitVec_And_IMP(BitVector *self, const BitVector *other) {
// Set all remaining to zero.
if (ivars->cap > min_cap) {
- const size_t self_byte_size = (size_t)ceil(ivars->cap / 8.0);
+ const size_t self_byte_size = (ivars->cap + 7) / 8;
memset(bits_a, 0, self_byte_size - byte_size);
}
}
@@ -273,7 +271,7 @@ S_do_or_or_xor(BitVector *self, const BitVector *other, int
operation) {
if (max_cap > ivars->cap) { BitVec_Grow(self, max_cap); }
bits_a = ivars->bits;
bits_b = ovars->bits;
- byte_size = ceil(min_cap / 8.0);
+ byte_size = (min_cap + 7) / 8;
limit = ivars->bits + (size_t)byte_size;
// Perform union of common bits.
@@ -295,7 +293,7 @@ S_do_or_or_xor(BitVector *self, const BitVector *other, int
operation) {
// Copy remaining bits if other is bigger than self.
if (ovars->cap > min_cap) {
- const double other_byte_size = ceil(ovars->cap / 8.0);
+ const double other_byte_size = (ovars->cap + 7) / 8;
const size_t bytes_to_copy = (size_t)(other_byte_size - byte_size);
memcpy(bits_a, bits_b, bytes_to_copy);
}
@@ -310,7 +308,7 @@ BitVec_And_Not_IMP(BitVector *self, const BitVector *other)
{
const uint32_t min_cap = ivars->cap < ovars->cap
? ivars->cap
: ovars->cap;
- const size_t byte_size = (size_t)ceil(min_cap / 8.0);
+ const size_t byte_size = (min_cap + 7) / 8;
uint8_t *const limit = bits_a + byte_size;
// Clear bits set in other.
@@ -377,7 +375,7 @@ uint32_t
BitVec_Count_IMP(BitVector *self) {
BitVectorIVARS *const ivars = BitVec_IVARS(self);
uint32_t count = 0;
- const size_t byte_size = (size_t)ceil(ivars->cap / 8.0);
+ const size_t byte_size = (ivars->cap + 7) / 8;
uint8_t *ptr = ivars->bits;
uint8_t *const limit = ptr + byte_size;
@@ -395,7 +393,7 @@ BitVec_To_Array_IMP(BitVector *self) {
uint32_t num_left = count;
const uint32_t capacity = ivars->cap;
uint32_t *const array = (uint32_t*)CALLOCATE(count, sizeof(uint32_t));
- const size_t byte_size = (size_t)ceil(ivars->cap / 8.0);
+ const size_t byte_size = (ivars->cap + 7) / 8;
uint8_t *const bits = ivars->bits;
uint8_t *const limit = bits + byte_size;
uint32_t num = 0;
http://git-wip-us.apache.org/repos/asf/lucy/blob/04bd80fe/core/Lucy/Test/Search/TestSeriesMatcher.c
----------------------------------------------------------------------
diff --git a/core/Lucy/Test/Search/TestSeriesMatcher.c
b/core/Lucy/Test/Search/TestSeriesMatcher.c
index f8a355a..b6c949b 100644
--- a/core/Lucy/Test/Search/TestSeriesMatcher.c
+++ b/core/Lucy/Test/Search/TestSeriesMatcher.c
@@ -17,7 +17,6 @@
#define C_TESTLUCY_TESTSERIESMATCHER
#define TESTLUCY_USE_SHORT_NAMES
#include "Lucy/Util/ToolSet.h"
-#include <math.h>
#include "Clownfish/TestHarness/TestBatchRunner.h"
#include "Lucy/Test.h"
@@ -62,7 +61,7 @@ S_make_series_matcher(I32Array *doc_ids, I32Array *offsets,
int32_t doc_max) {
static I32Array*
S_generate_match_list(int32_t first, int32_t max, int32_t doc_inc) {
- int32_t count = (int32_t)ceil(((float)max - first) / doc_inc);
+ int32_t count = (max - first + doc_inc - 1) / doc_inc;
int32_t *doc_ids = (int32_t*)MALLOCATE(count * sizeof(int32_t));
int32_t doc_id = first;
int32_t i = 0;
