Re: [PATCH 3/3] commit-slab: introduce a macro to define a slab for new type
Jeff King writes: > On Sat, Apr 13, 2013 at 11:04:49PM -0700, Junio C Hamano wrote: > >> Suppose you want to give one bit per existing ref and paint commits >> down to find which refs are descendants of each commit. You find >> that you have 320 refs only at runtime. >> >> The code can declare a commit slab "struct flagbits" >> >> define_commit_slab(flagbits, unsigned char); >> struct flagbits flags; >> >> and initialize it by: >> >> nrefs = ... count number of refs that returns say 320 ... >> init_flagbits_with_stride(&flags, (nrefs + 7) / 8); >> >> so that >> >> unsigned char *fp = flagbits_at(&flags, commit); >> >> will return a pointer pointing at an array of 40 "unsigned char"s >> associated with the commit. > > Thanks, I was thinking originally that we would want to break it down > into "unsigned long" or something, but there is probably no real > performance advantage to doing that over bytes. The 320 came from writing "an array of 5 unsigned long long" in the first draft ;-) > I'd probably further wrap it with a flagbit_set and flagbit_tst to wrap > the "figure out which byte, then which bit of that byte" logic, but that > would be a wrapper around flagbits_at, anyway. It can come later. Exactly. At that point, it is not about "what you could use commit slab for" but is about "how you would implement unbounded set of flag bits". > We'd probably want the hot path of this (returning the actual pointer) > to be inline, but not necessarily the parts about growing,... Yeah, this was just a technology demonstration as your original. -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH 3/3] commit-slab: introduce a macro to define a slab for new type
On Sat, Apr 13, 2013 at 11:04:49PM -0700, Junio C Hamano wrote:
> Suppose you want to give one bit per existing ref and paint commits
> down to find which refs are descendants of each commit. You find
> that you have 320 refs only at runtime.
>
> The code can declare a commit slab "struct flagbits"
>
> define_commit_slab(flagbits, unsigned char);
> struct flagbits flags;
>
> and initialize it by:
>
> nrefs = ... count number of refs that returns say 320 ...
> init_flagbits_with_stride(&flags, (nrefs + 7) / 8);
>
> so that
>
> unsigned char *fp = flagbits_at(&flags, commit);
>
> will return a pointer pointing at an array of 40 "unsigned char"s
> associated with the commit.
Thanks, I was thinking originally that we would want to break it down
into "unsigned long" or something, but there is probably no real
performance advantage to doing that over bytes.
I'd probably further wrap it with a flagbit_set and flagbit_tst to wrap
the "figure out which byte, then which bit of that byte" logic, but that
would be a wrapper around flagbits_at, anyway. It can come later.
> +static elemtype *slabname## _at(struct slabname *s, \
> + const struct commit *c) \
> +{\
> + int nth_slab, nth_slot, ix; \
> + \
> + ix = c->index * s->stride; \
> + nth_slab = ix / s->slab_size; \
> + nth_slot = ix % s->slab_size; \
> + \
> + if (s->slab_count <= nth_slab) {\
> + int i; \
> + s->slab = xrealloc(s->slab, \
> +(nth_slab + 1) * sizeof(s->slab)); \
> + stat_ ##slabname## realloc++; \
> + for (i = s->slab_count; i <= nth_slab; i++) \
> + s->slab[i] = NULL; \
> + s->slab_count = nth_slab + 1; \
> + } \
> + if (!s->slab[nth_slab]) \
> + s->slab[nth_slab] = xcalloc(s->slab_size, \
> + sizeof(**s->slab)); \
> + return &s->slab[nth_slab][nth_slot];\
> +}\
We'd probably want the hot path of this (returning the actual pointer)
to be inline, but not necessarily the parts about growing, which should
trigger a lot less. It may make sense to split the conditional bodies
out into a sub-function. And do we want to mark it with "inline"?
-Peff
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
[PATCH 3/3] commit-slab: introduce a macro to define a slab for new type
Introduce a header file to define a macro that can define the struct
type, initializer, accessor and cleanup functions to manage a commit
slab. Update the "indegree" topological sort facility using it.
To associate 32 flag bits with each commit,
you can write:
define_commit_slab(flag32, uint32);
to declare "struct flag32" type, define an instance of it with
struct flag32 flags;
and initialize it by calling
init_flag32(&flags);
After that,
uint32 *fp = flag32_at(&flags, commit);
will return a pointer pointing at a uint32 for that commit. Once
you are done with these flags, clean them up with
clear_flag32(&flags);
Callers that cannot hard-code how wide the data to be associated
with the commit be at compile time can use the "stride" variant.
Suppose you want to give one bit per existing ref and paint commits
down to find which refs are descendants of each commit. You find
that you have 320 refs only at runtime.
The code can declare a commit slab "struct flagbits"
define_commit_slab(flagbits, unsigned char);
struct flagbits flags;
and initialize it by:
nrefs = ... count number of refs that returns say 320 ...
init_flagbits_with_stride(&flags, (nrefs + 7) / 8);
so that
unsigned char *fp = flagbits_at(&flags, commit);
will return a pointer pointing at an array of 40 "unsigned char"s
associated with the commit.
Signed-off-by: Junio C Hamano
---
commit-slab.h | 95 +++
commit.c | 69 +++
2 files changed, 105 insertions(+), 59 deletions(-)
create mode 100644 commit-slab.h
diff --git a/commit-slab.h b/commit-slab.h
new file mode 100644
index 000..8030885
--- /dev/null
+++ b/commit-slab.h
@@ -0,0 +1,95 @@
+#ifndef COMMIT_SLAB_H
+#define COMMIT_SLAB_H
+
+/*
+ * define_commit_slab(slabname, elemtype) creates boilerplate code to define
+ * a new struct (struct slabname) that is used to associate a piece of data
+ * of elemtype to commits, and a few functions to use that struct.
+ *
+ * After including this header file, using:
+ *
+ * define_commit_slab(indegee, int);
+ *
+ * will let you call the following functions:
+ *
+ * - int *indegree_at(struct indegree *, struct commit *);
+ *
+ * This function locates the data associated with the given commit in
+ * the indegree slab, and returns the pointer to it.
+ *
+ * - void init_indegree(struct indegree *, int stride);
+ *
+ * Initializes the indegree slab that associates an array of integers
+ * to each commit. 'stride' specifies how big each array is.
+ */
+
+/* allocate ~512kB at once, allowing for malloc overhead */
+#ifndef COMMIT_SLAB_SIZE
+#define COMMIT_SLAB_SIZE (512*1024-32)
+#endif
+
+#define define_commit_slab(slabname, elemtype)
\
+ \
+struct slabname { \
+ unsigned slab_size; \
+ unsigned stride;\
+ unsigned slab_count;\
+ elemtype **slab;\
+}; \
+static int stat_ ##slabname## realloc; \
+ \
+static void init_ ##slabname## _with_stride(struct slabname *s,
\
+ unsigned stride)\
+{ \
+ unsigned int elem_size; \
+ if (!stride)\
+ stride = 1; \
+ s->stride = stride; \
+ elem_size = sizeof(struct slabname) * stride; \
+ s->slab_size = COMMIT_SLAB_SIZE / elem_size;\
+ s->slab_count = 0; \
+ s->slab = NULL; \
+} \
+ \
+static void init_ ##slabname(struct slabname *s) \
+{ \
+ init_ ##slabname## _with_stride(s, 1); \
+} \
+ \
+static void clear_ ##slabname(struct slabname *s) \
+{
