Changeset 562d8f in git

Timestamp:

Jul 10, 2019, 7:46:35 PM (5 years ago)

Author:

tthsqe12 <tthsqe12@…>

Branches:

(u'spielwiese', '17f1d200f27c5bd38f5dfc6e8a0879242279d1d8')

Children:

2fb52dfda50207f5e8f1be93c4aed7752b7af4a1

Parents:

c36a59349478e81a9b576d5483791fd3ec54e789

Message:

opt: calculate bits in parallel conversion

File:

• libpolys/polys/flint_mpoly.cc (modified) (16 diffs)

libpolys/polys/flint_mpoly.cc

@@ -64 +64 @@
 
 #if 1
-// malloc is not thread safe; singular polynomials must be constructed in serial
+// memory allocation is not thread safe; singular polynomials must be constructed in serial
 
 void convSingPFlintMP(fmpq_mpoly_t res, fmpq_mpoly_ctx_t ctx, poly p, int lp, const ring r)
@@ -165 +165 @@
 
 #else
-// malloc is thread safe; singular polynomials may be constructed in serial
+// memory allocator is thread safe; singular polynomials may be constructed in parallel
 
 // like convSingNFlintN_QQ but it takes an initialized fmpq_t f
@@ -199 +199 @@
 
     convert_sing_to_fmpq_mpoly_base(slong num_threads_, fmpq_mpoly_struct * res_,
-                             const fmpq_mpoly_ctx_struct * ctx_, const ring r_)
+                             const fmpq_mpoly_ctx_struct * ctx_, const ring r_, poly p)
       : num_threads(num_threads_),
         res(res_),
@@ -205 +205 @@
         r(r_)
     {
-    }
-
-    void init_poly(poly p)
-    {
         length = 0;
-        while (p != NULL)
+        while (1)
         {
-            markers.push_back(p);
-            for (int i = 4096; i > 0; i--)
-            {
-                pIter(p);
-                length++;
-                if (p == NULL)
-                    break;
-            }
+            if ((length % 4096) == 0)
+                markers.push_back(p);
+            if (p == NULL)
+                return;
+            length++;
+            pIter(p);
         }
-
-        fmpq_mpoly_init3(res, length, SI_LOG2(r->bitmask), ctx);
     }
 };
@@ -232 +224 @@
     slong start_idx, end_idx;
     convert_sing_to_fmpq_mpoly_base* base;
+    flint_bitcnt_t required_bits;
 
     convert_sing_to_fmpq_mpoly_arg() {fmpq_init(content);}
@@ -237 +230 @@
 };
 
-static void convert_sing_to_fmpq_mpoly_content_worker(void * varg)
+static void convert_sing_to_fmpq_mpoly_content_bits(void * varg)
 {
     convert_sing_to_fmpq_mpoly_arg* arg = (convert_sing_to_fmpq_mpoly_arg*) varg;
+    convert_sing_to_fmpq_mpoly_base * base = arg->base;
+    ulong * exp = (ulong*) flint_malloc((base->r->N + 1)*sizeof(ulong));
     fmpq_t c;
     fmpq_init(c);
@@ -252 +247 @@
     }
 
-    /* first find gcd of coeffs */
+    flint_bitcnt_t required_bits = MPOLY_MIN_BITS;
     fmpq_zero(arg->content);
+
     while (idx < arg->end_idx)
     {
         my_convSingNFlintN_QQ(c, number(pGetCoeff(p)));
         fmpq_gcd(arg->content, arg->content, c);
+
+        #if SIZEOF_LONG==8
+        p_GetExpVL(p, (int64*)exp, base->r);
+        flint_bitcnt_t exp_bits = mpoly_exp_bits_required_ui(exp, base->ctx->zctx->minfo);
+        #else
+        p_GetExpV(p, (int*)exp, base->r);
+        flint_bitcnt_t exp_bits = mpoly_exp_bits_required_ui(&(exp[1]), base->ctx->zctx->minfo);
+        #endif
+
+        required_bits = FLINT_MAX(required_bits, exp_bits);
+
         pIter(p);
         idx++;
     }
 
+    arg->required_bits = required_bits;
+
     fmpq_clear(c);
+    flint_free(exp);
 }
 
@@ -330 +340 @@
     }
 
-    convert_sing_to_fmpq_mpoly_base base(num_handles + 1, res, ctx, r);
-    base.init_poly(p);
-
+    convert_sing_to_fmpq_mpoly_base base(num_handles + 1, res, ctx, r, p);
+
+    /* fill in thread division points */
     convert_sing_to_fmpq_mpoly_arg * args = new convert_sing_to_fmpq_mpoly_arg[base.num_threads];
     slong cur_idx = 0;
@@ -346 +356 @@
     }
 
-    /* get content */
-    for (slong i = 0; i < num_handles; i++)
-        thread_pool_wake(global_thread_pool, handles[i], convert_sing_to_fmpq_mpoly_content_worker, args + i);
-    convert_sing_to_fmpq_mpoly_content_worker(args + num_handles);
-    for (slong i = 0; i < num_handles; i++)
-    {
+    /* get content and bits */
+    for (slong i = 0; i < num_handles; i++)
+        thread_pool_wake(global_thread_pool, handles[i], convert_sing_to_fmpq_mpoly_content_bits, args + i);
+    convert_sing_to_fmpq_mpoly_content_bits(args + num_handles);
+    for (slong i = 0; i < num_handles; i++)
         thread_pool_wait(global_thread_pool, handles[i]);
-    }
+
+    flint_bitcnt_t required_bits = MPOLY_MIN_BITS;
+    for (slong i = 0; i <= num_handles; i++)
+        required_bits = FLINT_MAX(required_bits, args[i].required_bits);
+
+    /* initialize res with optimal bits */
+    fmpq_mpoly_init3(res, base.length, mpoly_fix_bits(required_bits, ctx->zctx->minfo), ctx);
 
     /* sign of content should match sign of first coeff */
@@ -418 +433 @@
     convert_fmpq_mpoly_to_sing_arg * arg = (convert_fmpq_mpoly_to_sing_arg *) varg;
     convert_fmpq_mpoly_to_sing_base * base = arg->base;
-    ulong* exp = (ulong*) flint_calloc(base->r->N + 1, sizeof(ulong));
+    ulong* exp = (ulong*) flint_malloc((base->r->N + 1)*sizeof(ulong));
     fmpq_t c;
     fmpq_init(c);
@@ -528 +543 @@
 
     convert_sing_to_nmod_mpoly_base(slong num_threads_, nmod_mpoly_struct * res_,
-                            const nmod_mpoly_ctx_struct * ctx_, const ring r_)
+                            const nmod_mpoly_ctx_struct * ctx_, const ring r_, poly p)
       : num_threads(num_threads_),
         res(res_),
@@ -534 +549 @@
         r(r_)
     {
-    }
-
-    void init_poly(poly p)
-    {
         length = 0;
-        while (p != NULL)
+        while (1)
         {
-            markers.push_back(p);
-            for (int i = 4096; i > 0; i--)
-            {
-                pIter(p);
-                length++;
-                if (p == NULL)
-                    break;
-            }
+            if ((length % 4096) == 0)
+                markers.push_back(p);
+            if (p == NULL)
+                return;
+            length++;
+            pIter(p);
         }
-
-        nmod_mpoly_init3(res, length, SI_LOG2(r->bitmask), ctx);
     }
 };
@@ -560 +567 @@
     slong start_idx, end_idx;
     convert_sing_to_nmod_mpoly_base* base;
+    flint_bitcnt_t required_bits;
 };
+
+static void convert_sing_to_nmod_mpoly_bits(void * varg)
+{
+    convert_sing_to_nmod_mpoly_arg * arg = (convert_sing_to_nmod_mpoly_arg *) varg;
+    convert_sing_to_nmod_mpoly_base * base = arg->base;
+    ulong * exp = (ulong*) flint_malloc((base->r->N + 1)*sizeof(ulong));
+
+    slong idx = arg->start_idx/4096;
+    poly p = base->markers[idx];
+    idx *= 4096;
+    while (idx < arg->start_idx)
+    {
+        pIter(p);
+        idx++;
+    }
+
+    flint_bitcnt_t required_bits = MPOLY_MIN_BITS;
+
+    while (idx < arg->end_idx)
+    {
+        #if SIZEOF_LONG==8
+        p_GetExpVL(p, (int64*)exp, base->r);
+        flint_bitcnt_t exp_bits = mpoly_exp_bits_required_ui(exp, base->ctx->minfo);
+        #else
+        p_GetExpV(p, (int*)exp, base->r);
+        flint_bitcnt_t exp_bits = mpoly_exp_bits_required_ui(&(exp[1]), base->ctx->minfo);
+        #endif
+
+        required_bits = FLINT_MAX(required_bits, exp_bits);
+
+        pIter(p);
+        idx++;
+    }
+
+    arg->required_bits = required_bits;
+
+    flint_free(exp);
+}
+
 
 static void convert_sing_to_nmod_mpoly_worker(void * varg)
@@ -618 +665 @@
     }
 
-    convert_sing_to_nmod_mpoly_base base(num_handles + 1, res, ctx, r);
-    base.init_poly(p);
-
+    convert_sing_to_nmod_mpoly_base base(num_handles + 1, res, ctx, r, p);
+
+    /* fill in thread division points */
     convert_sing_to_nmod_mpoly_arg * args = new convert_sing_to_nmod_mpoly_arg[base.num_threads];
     slong cur_idx = 0;
@@ -635 +682 @@
     }
 
+    /* find required bits */
+    for (slong i = 0; i < num_handles; i++)
+        thread_pool_wake(global_thread_pool, handles[i], convert_sing_to_nmod_mpoly_bits, args + i);
+    convert_sing_to_nmod_mpoly_bits(args + num_handles);
+    for (slong i = 0; i < num_handles; i++)
+        thread_pool_wait(global_thread_pool, handles[i]);
+
+    flint_bitcnt_t required_bits = MPOLY_MIN_BITS;
+    for (slong i = 0; i <= num_handles; i++)
+        required_bits = FLINT_MAX(required_bits, args[i].required_bits);
+
+    /* initialize res with optimal bits */
+    nmod_mpoly_init3(res, base.length, mpoly_fix_bits(required_bits, ctx->minfo), ctx);
+
     /* fill in res */
     for (slong i = 0; i < num_handles; i++)
@@ -685 +746 @@
     convert_nmod_mpoly_to_sing_arg * arg = (convert_nmod_mpoly_to_sing_arg *) varg;
     convert_nmod_mpoly_to_sing_base * base = arg->base;
-    ulong* exp = (ulong*) flint_calloc(base->r->N + 1, sizeof(ulong));
+    ulong* exp = (ulong*) flint_malloc((base->r->N + 1)*sizeof(ulong));
 
     for (slong idx = arg->end_idx - 1; idx >= arg->start_idx; idx--)