Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
cdbw optimisation in libc
4 views
Skip to first unread message
Alexander Nasonov
Jul 2, 2015, 4:03:43 PM7/2/15
to
Hi,
I recently came across an interesting article [1] which introduces
a simpler algorithm for chm3 hash generation. The key idea is that
incidence lists can be eliminated by using a clever XOR trick.
The patch of the new implementation is attached. It's faster than
the original algorithm but for some reason I only get about 20%
speedup on a Haswell notebook and 10% more by using fast_remainder32(3).
However, the new algorithm uses significantly less memory. In the
current implementation, edges, verts and output_order arrays take
16n 32-bit words (where n is a number of keys). I believe that there
is a typo in the edges array allocation (fixed in the attached patch)
and it allocates too much memory. The fix reduces memory size to
13.75n in the current implementation. My change brings it down to 9n.
Ok to commit?
[1] Cache-Oblivious Peeling of Random Hypergraphs by Djamal Belazzougui,
Paolo Boldi, Giuseppe Ottaviano, Rossano Venturini, and Sebastiano Vigna.
Alex
I recently came across an interesting article [1] which introduces
a simpler algorithm for chm3 hash generation. The key idea is that
incidence lists can be eliminated by using a clever XOR trick.
The patch of the new implementation is attached. It's faster than
the original algorithm but for some reason I only get about 20%
speedup on a Haswell notebook and 10% more by using fast_remainder32(3).
However, the new algorithm uses significantly less memory. In the
current implementation, edges, verts and output_order arrays take
16n 32-bit words (where n is a number of keys). I believe that there
is a typo in the edges array allocation (fixed in the attached patch)
and it allocates too much memory. The fix reduces memory size to
13.75n in the current implementation. My change brings it down to 9n.
Ok to commit?
[1] Cache-Oblivious Peeling of Random Hypergraphs by Djamal Belazzougui,
Paolo Boldi, Giuseppe Ottaviano, Rossano Venturini, and Sebastiano Vigna.
Alex
Joerg Sonnenberger
Jul 2, 2015, 4:28:59 PM7/2/15
to
On Thu, Jul 02, 2015 at 08:58:15PM +0100, Alexander Nasonov wrote:
> Ok to commit?
Won't survive in tools as is. Can't say more about the details of the
code ATM.
Joerg
--
Posted automagically by a mail2news gateway at muc.de e.V.
Please direct questions, flames, donations, etc. to news-...@muc.de
> Ok to commit?
Won't survive in tools as is. Can't say more about the details of the
code ATM.
Joerg
--
Posted automagically by a mail2news gateway at muc.de e.V.
Please direct questions, flames, donations, etc. to news-...@muc.de
Alexander Nasonov
Jul 2, 2015, 5:35:37 PM7/2/15
to
Joerg Sonnenberger wrote:
> Won't survive in tools as is.
Can you please elaborate?
> Won't survive in tools as is.
Is it because of this contruct
+remove_vertex(struct state *state, uint32_t v0)
+{
+ uint32_t e, v1, v2;
+ struct oedge *o = state->oedges;
or <sys/bitops.h> or something else?
Alex
Joerg Sonnenberger
Jul 2, 2015, 6:05:31 PM7/2/15
to
On Thu, Jul 02, 2015 at 10:35:19PM +0100, Alexander Nasonov wrote:
> Joerg Sonnenberger wrote:
> > Won't survive in tools as is.
>
> Joerg Sonnenberger wrote:
> > Won't survive in tools as is.
>
> Can you please elaborate?
>
> Is it because of this contruct
>
> +remove_vertex(struct state *state, uint32_t v0)
> +{
> + uint32_t e, v1, v2;
> + struct oedge *o = state->oedges;
>
>
> or <sys/bitops.h> or something else?
Use of sys/bitops.h.
>
> Is it because of this contruct
>
> +remove_vertex(struct state *state, uint32_t v0)
> +{
> + uint32_t e, v1, v2;
> + struct oedge *o = state->oedges;
>
>
> or <sys/bitops.h> or something else?
Alexander Nasonov
Jul 2, 2015, 6:16:50 PM7/2/15
to
Joerg Sonnenberger wrote:
> Use of sys/bitops.h.
Ah, ok, those bits can be trivially reverted.
Alex
> Use of sys/bitops.h.
Ah, ok, those bits can be trivially reverted.
Alex
Alexander Nasonov
Jul 4, 2015, 10:02:08 AM7/4/15
to
Alexander Nasonov wrote:
> The patch of the new implementation is attached. It's faster than
> the original algorithm but for some reason I only get about 20%
> speedup on a Haswell notebook and 10% more by using fast_remainder32(3).
If the algorithm starts with a good seed, the speedup is about 50%.
> The patch of the new implementation is attached. It's faster than
> the original algorithm but for some reason I only get about 20%
> speedup on a Haswell notebook and 10% more by using fast_remainder32(3).
A significant amount of time can be spent trying to find a good
hypergraph, that is, a hypergraph without identical vertices in
all edges. IIRC, a probability of generating an edge with identical
vertices is around 0.8-0.9.
0 new messages