lucy-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From nwelln...@apache.org
Subject [1/3] lucy git commit: Improve integer division with rounded-up result
Date Thu, 24 Mar 2016 11:53:11 GMT
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 <wellnhofer@aevum.de>
Authored: Sun Mar 20 23:13:32 2016 +0100
Committer: Nick Wellnhofer <wellnhofer@aevum.de>
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;


Mime
View raw message