[hackers] [libzahl] Optimisations || Mattias Andrée
commit 92be5631d8e319babf5cca49f53ea5e692c54793
Author: Mattias Andrée
AuthorDate: Tue Mar 15 00:20:00 2016 +0100
Commit: Mattias Andrée
CommitDate: Tue Mar 15 00:20:00 2016 +0100
Optimisations
Signed-off-by: Mattias Andrée
diff --git a/Makefile b/Makefile
index c340bf6..c256d4c 100644
--- a/Makefile
+++ b/Makefile
@@ -8,11 +8,6 @@ FUN =\
zadd\
zand\
zbset\
- zbtest\
- zcmp\
- zcmpi\
- zcmpmag\
- zcmpu\
zdiv\
zdivmod\
zerror\
@@ -61,7 +56,12 @@ INLINE_FUN =\
zneg\
zlsb\
zbits\
- zseti
+ zseti\
+ zcmp\
+ zcmpi\
+ zcmpmag\
+ zcmpu\
+ zbtest
OBJ = $(FUN:=.o) allocator.o
MAN3 = $(FUN:=.3) $(INLINE_FUN:=.3)
diff --git a/TODO b/TODO
index a71124e..23edfbf 100644
--- a/TODO
+++ b/TODO
@@ -3,3 +3,8 @@ It uses optimised division algorithm that requires that d|n.
Add zsets_radix
Add zstr_radix
+Add zranddist value based on % for fitness to bound
+
+Test big endian
+Test always having used > 0 for zero
+ Test negative/non-negative instead of sign
diff --git a/src/zadd.c b/src/zadd.c
index 2d42684..557ec6f 100644
--- a/src/zadd.c
+++ b/src/zadd.c
@@ -21,8 +21,8 @@ zadd_impl(z_t a, z_t b, size_t n)
a->used = i;
}
-inline void
-zadd_unsigned(z_t a, z_t b, z_t c)
+static inline void
+libzahl_zadd_unsigned(z_t a, z_t b, z_t c)
{
size_t size, n;
@@ -66,6 +66,12 @@ zadd_unsigned(z_t a, z_t b, z_t c)
}
void
+zadd_unsigned(z_t a, z_t b, z_t c)
+{
+ libzahl_zadd_unsigned(a, b, c);
+}
+
+void
zadd(z_t a, z_t b, z_t c)
{
if (unlikely(zzero(b))) {
@@ -74,7 +80,7 @@ zadd(z_t a, z_t b, z_t c)
SET(a, b);
} else if (unlikely(znegative(b))) {
if (znegative(c)) {
- zadd_unsigned(a, b, c);
+ libzahl_zadd_unsigned(a, b, c);
SET_SIGNUM(a, -zsignum(a));
} else {
zsub_unsigned(a, c, b);
@@ -82,6 +88,6 @@ zadd(z_t a, z_t b, z_t c)
} else if (unlikely(znegative(c))) {
zsub_unsigned(a, b, c);
} else {
- zadd_unsigned(a, b, c);
+ libzahl_zadd_unsigned(a, b, c);
}
}
diff --git a/src/zbset.c b/src/zbset.c
index 2874238..cc7b2b0 100644
--- a/src/zbset.c
+++ b/src/zbset.c
@@ -2,38 +2,45 @@
#include "internals.h"
-void
-zbset(z_t a, z_t b, size_t bit, int action)
-{
- zahl_char_t mask = 1;
- size_t chars;
-
- chars = FLOOR_BITS_TO_CHARS(bit);
- bit = BITS_IN_LAST_CHAR(bit);
- mask <<= bit;
+#define PROLOGUE(MAY_INCREASE)\
+ zahl_char_t mask = 1;\
+ size_t chars = FLOOR_BITS_TO_CHARS(bit);\
+ if (MAY_INCREASE) {\
+ if (zzero(a)) {\
+ a->used = 0;\
+ SET_SIGNUM(a, 1);\
+ }\
+ if (unlikely(chars >= a->used)) {\
+ ENSURE_SIZE(a, chars + 1);\
+ zmemset(a->chars + a->used, 0, chars + 1 - a->used);\
+ a->used = chars + 1;\
+ }\
+ } else if (unlikely(chars >= a->used)) {\
+ return;\
+ }\
+ bit = BITS_IN_LAST_CHAR(bit);\
+ mask <<= bit
- SET(a, b);
- if (action) {
- if (zzero(a)) {
- a->used = 0;
- SET_SIGNUM(a, 1);
- }
- if (a->used <= chars) {
- ENSURE_SIZE(a, chars + 1);
- zmemset(a->chars + a->used, 0, chars + 1 - a->used);
- a->used = chars + 1;
- }
- }
+void
+zbset_impl_set(z_t a, z_t b, size_t bit)
+{
+ PROLOGUE(1);
+ a->chars[chars] |= mask;
+}
- if (action > 0) {
- a->chars[chars] |= mask;
- return;
- } else if (action < 0) {
- a->chars[chars] ^= mask;
- } else if (chars < a->used) {
- a->chars[chars] &= ~mask;
- }
+void
+zbset_impl_clear(z_t a, z_t b, size_t bit)
+{
+ PROLOGUE(0);
+ a->chars[chars] &= ~mask;
+ TRIM_AND_ZERO(a);
+}
+void
+zbset_impl_flip(z_t a, z_t b, size_t bit)
+{
+ PROLOGUE(1);
+ a->chars[chars] ^= mask;
TRIM_AND_ZERO(a);
}
diff --git a/src/zbtest.c b/src/zbtest.c
deleted file mode 100644
index a97e714..000
--- a/src/zbtest.c
+++ /dev/null
@@ -1,18 +0,0 @@
-/* See LICENSE file for copyright and license details. */
-#include "internals.h"
-
-
-int
-zbtest(z_t a, size_t bit)
-{
- size_t chars;
- if (zzero(a))
- return 0;
-
- chars = FLOOR_BITS_TO_CHARS(bit);
- if (chars >= a->used)
- return 0;
-
- bit = BITS_IN_LAST_CHAR(bit);
- return (a->chars[chars] >> bit) & 1;
-}
diff --git a/src/zcmp.c b/src/zcmp.c
deleted file mode 100644
index 55caa6b..
[hackers] [libzahl] Optimise zswap || Mattias Andrée
commit 1ec80039288073294e3e61b0c680e9c95688e786
Author: Mattias Andrée
AuthorDate: Mon Mar 14 20:51:37 2016 +0100
Commit: Mattias Andrée
CommitDate: Mon Mar 14 20:51:37 2016 +0100
Optimise zswap
Signed-off-by: Mattias Andrée
diff --git a/zahl.h b/zahl.h
index 37711b2..9a03b26 100644
--- a/zahl.h
+++ b/zahl.h
@@ -189,7 +189,6 @@ void zperror(const char *); /* Identical to
perror(3p) except it sup
ZAHL_INLINE void zinit(z_t a) { a->alloced = 0; a->chars = 0; }
-ZAHL_INLINE void zswap(z_t a, z_t b) { z_t t; *t = *a; *a = *b; *b = *t; }
ZAHL_INLINE int zeven(z_t a) { return !a->sign || !(a->chars[0] & 1);
}
ZAHL_INLINE int zodd(z_t a) { return a->sign && (a->chars[0] & 1); }
ZAHL_INLINE int zeven_nonzero(z_t a) { return !(a->chars[0] & 1); }
@@ -201,6 +200,25 @@ ZAHL_INLINE void zneg(z_t a, z_t b) { if (a != b)
zset(a, b); a->sign = -a->si
ZAHL_INLINE void
+zswap(z_t a, z_t b)
+{
+ z_t t;
+ t->sign = a->sign;
+ a->sign = b->sign;
+ b->sign = t->sign;
+ t->used = b->used;
+ b->used = a->used;
+ a->used = t->used;
+ t->alloced = a->alloced;
+ a->alloced = b->alloced;
+ b->alloced = t->alloced;
+ t->chars = b->chars;
+ b->chars = a->chars;
+ a->chars = t->chars;
+}
+
+
+ZAHL_INLINE void
zseti(z_t a, int64_t b)
{
if (ZAHL_UNLIKELY(b >= 0)) {
[hackers] [farbfeld] Bump version to 2 || FRIGN
commit 49cef794d9cef3c1ab8478963a7f778c8c28eb70 Author: FRIGN AuthorDate: Mon Mar 14 23:12:49 2016 +0100 Commit: FRIGN CommitDate: Mon Mar 14 23:12:49 2016 +0100 Bump version to 2 There have been quite considerable changes since version 1. The conversion tools have had a considerable performance boost of around 75% by using a row-buffer instead of reading each R-G-B-A-chunk individually. Also, 2ff(1) somehow called "xconvert" instead of "convert", rendering it useless for anything other than png's and jpg's. There was a small excursion to color spaces and ICC color profile handling, but this has been dismissed (it was a difficult decision). Thanks for all the feedback! diff --git a/config.mk b/config.mk index 37ad05f..94a4570 100644 --- a/config.mk +++ b/config.mk @@ -1,5 +1,5 @@ # farbfeld version -VERSION = 1 +VERSION = 2 # Customize below to fit your system
[hackers] [sbase][PATCH] diff: Remove support for coloured output and do not refer to -e in description of -f
Signed-off-by: Mattias Andrée
---
Makefile | 1 -
bdiff.1| 10 +++--
diff.1 | 10 +++--
diff.c | 65 +++---
libutil/ncprintf.c | 50 -
util.h | 1 -
6 files changed, 34 insertions(+), 103 deletions(-)
delete mode 100644 libutil/ncprintf.c
diff --git a/Makefile b/Makefile
index f17268b..61f5b25 100644
--- a/Makefile
+++ b/Makefile
@@ -60,7 +60,6 @@ LIBUTILSRC =\
libutil/md5.c\
libutil/mkdirp.c\
libutil/mode.c\
- libutil/ncprintf.c\
libutil/parseoffset.c\
libutil/putword.c\
libutil/reallocarray.c\
diff --git a/bdiff.1 b/bdiff.1
index 1e114d6..d793215 100644
--- a/bdiff.1
+++ b/bdiff.1
@@ -7,7 +7,7 @@
.Sh SYNOPSIS
.Nm
.Op Fl c | C Ar n | Fl e | f | u | U Ar n
-.Op Fl bdDr
+.Op Fl bdr
.Ar file1 file2
.Sh DESCRIPTION
.Nm
@@ -39,15 +39,11 @@ is -1, use the entire file for context.
.It Fl d
Ignored. Exists for symmetry with
.Xr diff 1 .
-.It Fl D
-Produce colored output if stdout, is a terminal.
-Always produce colored output if used twice or more.
.It Fl e
Produce output suitable as input to
.Xr ed 1 .
.It Fl f
-Produce output similar to the format of
-.Fl e ,
+Produce \fIed\fP-script like output,
but intended for reading by a human.
.It Fl r
Apply
@@ -66,7 +62,7 @@ lines of unified context. If
is -1, use the entire file for context.
.El
.Sh EXIT STATUS
-.Bl -tag -width Ds
+.Bl -tag -width s
.It 0
The files are identical.
.It 1
diff --git a/diff.1 b/diff.1
index 1898c84..0f4362c 100644
--- a/diff.1
+++ b/diff.1
@@ -7,7 +7,7 @@
.Sh SYNOPSIS
.Nm
.Op Fl c | C Ar n | Fl e | f | u | U Ar n
-.Op Fl bdDr
+.Op Fl bdr
.Ar file1 file2
.Sh DESCRIPTION
.Nm
@@ -46,15 +46,11 @@ Do not fall back to behave like
.Xr bdiff 1 ,
even if its appears to be impossible to calculate
the minimal set of changes.
-.It Fl D
-Produce colored output if stdout, is a terminal.
-Always produce colored output if used twice or more.
.It Fl e
Produce output suitable as input to
.Xr ed 1 .
.It Fl f
-Produce output similar to the format of
-.Fl e ,
+Produce \fIed\fP-script like output,
but intended for reading by a human.
.It Fl r
Apply
@@ -103,5 +99,5 @@ determined to be feasible to calculate with generally
exceptable time and memory usage.
.Pp
The
-.Op Fl dD
+.Op Fl d
flags is an extension to that specification.
diff --git a/diff.c b/diff.c
index 8abcbcd..639361f 100644
--- a/diff.c
+++ b/diff.c
@@ -48,7 +48,6 @@
#define END_OF_PATH 127
#define NO_LF_MARK "\n\\ No newline at end of file"
-#define COLOURED_NO_LF_MARK "\n\033[7m\\ No newline at end of file\033[27m"
#define line_eq(a, b) ((a)->hash == (b)->hash && !strcmp((a)->line,
(b)->line))
#define intcmp(a, b) ((a) < (b) ? -1 : (a) > (b))
@@ -107,14 +106,11 @@ static int bdiff = 0;
static int dflag = 0;
static int cheap_algorithm_used = 0;
-static int use_colour = 0;
-static int (*cprintf)(const char *, ...);
-
static void
usage(void)
{
- enprintf(FAILURE, "usage: %s [-c | -C n | -e | -f | -u | -U n] [-bdDr]
file1 file2\n", argv0);
+ enprintf(FAILURE, "usage: %s [-c | -C n | -e | -f | -u | -U n] [-bdr]
file1 file2\n", argv0);
}
static int
@@ -903,11 +899,11 @@ get_diff_chunks(struct trace *path, size_t an, size_t bn,
struct chunk **headp,
if (!path)\
return 0;\
if (diff_line)\
- cprintf("\033[1m%s %s %s\033[m\n", diff_line, old->path_quoted,
new->path_quoted)
+ printf("%s %s %s\n", diff_line, old->path_quoted,
new->path_quoted)
#define OUTPUT_HEAD(A, B, TIMEFUN)\
- cprintf("\033[1m"A" %s\033[21m\t%s\033[0m\n", old->path_quoted,
TIMEFUN(&(old->attr)));\
- cprintf("\033[1m"B" %s\033[21m\t%s\033[0m\n", new->path_quoted,
TIMEFUN(&(new->attr)))
+ printf(A" %s\t%s\n", old->path_quoted, TIMEFUN(&(old->attr)));\
+ printf(B" %s\t%s\n", new->path_quoted, TIMEFUN(&(new->attr)))
#define OUTPUT_QUEUE\
get_diff_chunks(path, old->line_count * !old->is_empty, new->line_count
* !new->is_empty, &head, &tail);\
@@ -964,18 +960,18 @@ output_unified(struct file_data *old, struct file_data
*new, const char *diff_li
}
if (suppressed) {
suppressed = 0;
- cprintf("\033[1;34m@@ -%zu", ai + 1 - !trace.a_len);
+ printf("@@ -%zu", ai + 1 - !trace.a_len);
if (trace.a_len != 1)
printf(",%zu", trace.a_len);
printf(" +%zu", bi + 1 - !trace.b_len);
if (trace.b_len != 1)
printf(",%zu", trace.b_len);
- cprintf(" @@\033[m\n");
+ printf(" @@\n");
}
if (f == 0)
printf(" %s\n", a[ai]);
Re: [hackers] [sbase][PATCH v4] Add diff(1) and bdiff(1)
Hi, > +.It Fl D > +Produce colored output if stdout, is a terminal. > +Always produce colored output if used twice or more. I'm totally against this feature. Programs that check against /dev/tty are not orthogonal and your implementation is not portable because you hardcoded the escape sequences in the code. I think is better don't colorize and let this work to colordiff(1). > +.Xr ed 1 . > +.It Fl f > +Produce output similar to the format of > +.Fl e , .Fl e? what is e? Both comments apply to diff and bdiff. Regards,
[hackers] [libzahl] Mostly optimisations || Mattias Andrée
commit b2c44d8c961090c2773f3a98d12fcafc7f5c5b2b
Author: Mattias Andrée
AuthorDate: Mon Mar 14 17:56:37 2016 +0100
Commit: Mattias Andrée
CommitDate: Mon Mar 14 17:56:37 2016 +0100
Mostly optimisations
Signed-off-by: Mattias Andrée
diff --git a/Makefile b/Makefile
index 80d3aa7..c340bf6 100644
--- a/Makefile
+++ b/Makefile
@@ -36,7 +36,6 @@ FUN =\
zrsh\
zsave\
zset\
- zseti\
zsets\
zsetu\
zsetup\
@@ -61,7 +60,8 @@ INLINE_FUN =\
zabs\
zneg\
zlsb\
- zbits
+ zbits\
+ zseti
OBJ = $(FUN:=.o) allocator.o
MAN3 = $(FUN:=.3) $(INLINE_FUN:=.3)
diff --git a/TODO b/TODO
index fbc847f..a71124e 100644
--- a/TODO
+++ b/TODO
@@ -1,2 +1,5 @@
GMP has mpz_divexact(q,n,d), we should have zdiv_exact(q,n,d).
It uses optimised division algorithm that requires that d|n.
+
+Add zsets_radix
+Add zstr_radix
diff --git a/config.mk b/config.mk
index a1be136..cad12d8 100644
--- a/config.mk
+++ b/config.mk
@@ -1,4 +1,4 @@
-VERSION = 0.0
+VERSION = 1.1
PREFIX = /usr/local
EXECPREFIX = $(PREFIX)
diff --git a/man/zcmpi.3 b/man/zcmpi.3
index eb786f8..22acf41 100644
--- a/man/zcmpi.3
+++ b/man/zcmpi.3
@@ -5,7 +5,7 @@ zcmpi - Compare a big integer and a signed integer
.nf
#include
-int zcmpi(z_t \fIa\fP, signed long long int \fIb\fP);
+int zcmpi(z_t \fIa\fP, int64_t \fIb\fP);
.fi
.SH DESCRIPTION
.B zcmpi
diff --git a/man/zcmpu.3 b/man/zcmpu.3
index b4703a9..63cbf09 100644
--- a/man/zcmpu.3
+++ b/man/zcmpu.3
@@ -5,7 +5,7 @@ zcmpu - Compare a big integer and an unsigned integer
.nf
#include
-int zcmpu(z_t \fIa\fP, unsigned long long int \fIb\fP);
+int zcmpu(z_t \fIa\fP, uint64_t \fIb\fP);
.fi
.SH DESCRIPTION
.B zcmpu
diff --git a/man/zseti.3 b/man/zseti.3
index 40d4aef..c2c589f 100644
--- a/man/zseti.3
+++ b/man/zseti.3
@@ -5,7 +5,7 @@ zseti - Set the value of a big integer to a signed integer.
.nf
#include
-void zseti(z_t \fIa\fP, signed long long int \fIb\fP);
+void zseti(z_t \fIa\fP, int64_t \fIb\fP);
.fi
.SH DESCRIPTION
.B zseti
diff --git a/man/zsetu.3 b/man/zsetu.3
index a0598a7..62b8202 100644
--- a/man/zsetu.3
+++ b/man/zsetu.3
@@ -5,7 +5,7 @@ zsetu - Set the value of a big integer to an unsigned integer.
.nf
#include
-void zsetu(z_t \fIa\fP, unsigned long long int \fIb\fP);
+void zsetu(z_t \fIa\fP, uint64_t \fIb\fP);
.fi
.SH DESCRIPTION
.B zseti
diff --git a/src/allocator.c b/src/allocator.c
index 44f7985..7737046 100644
--- a/src/allocator.c
+++ b/src/allocator.c
@@ -28,7 +28,7 @@ libzahl_realloc(z_t a, size_t need)
a->chars = new;
} else {
a->chars = realloc(a->chars, need * sizeof(zahl_char_t));
- if (!a->chars) {
+ if (unlikely(!a->chars)) {
if (!errno) /* sigh... */
errno = ENOMEM;
libzahl_failure(errno);
diff --git a/src/internals.h b/src/internals.h
index c1153ea..c859ce1 100644
--- a/src/internals.h
+++ b/src/internals.h
@@ -4,7 +4,11 @@
#include
#include
#include
-#include
+
+/* clang pretends to be GCC... */
+#if defined(__GNUC__) && defined(__clang__)
+# undef __GNUC__
+#endif
#define BITS_PER_CHAR64
#define LB_BITS_PER_CHAR 6
@@ -14,6 +18,32 @@
#define CEILING_BITS_TO_CHARS(bits) (((bits) + (BITS_PER_CHAR - 1)) >>
LB_BITS_PER_CHAR)
#define BITS_IN_LAST_CHAR(bits) ((bits) & (BITS_PER_CHAR - 1))
+#if defined(__GNUC__)
+# define O0 __attribute__((optimize("O0")))
+# define O1 __attribute__((optimize("O1")))
+# define O2 __attribute__((optimize("O2")))
+# define O3 __attribute__((optimize("O3")))
+# define Ofast __attribute__((optimize("Ofast")))
+# define Os __attribute__((optimize("Os")))
+# define Oz __attribute__((optimize("Os")))
+#elif defined(__clang__)
+# define O0 __attribute__((optnone))
+# define O1 /* Don't know how. */
+# define O2 /* Don't know how. */
+# define O3 /* Don't know how. */
+# define Ofast /* Don't know how. */
+# define Os /* Don't know how. */
+# define Oz /* Don't know how. */
+#else
+# define O0 /* Don't know how. */
+# define O1 /* Don't know how. */
+# define O2 /* Don't know how. */
+# define O3 /* Don't know how. */
+# define Ofast /* Don't know how. */
+# define Os /* Don't know how. */
+# define Oz /* Don't know how. */
+#endif
+
#define LIST_TEMPS\
X(libzahl_tmp_cmp)\
X(libzahl_tmp_str_num)\
@@ -77,13 +107,14 @@ extern size_t libzahl_pool_alloc[sizeof(size_t) * 8];
#define TRIM(a) for (; (a)->used && !(a)->chars[(a)->used
- 1]; (a)->used--)
#define TRIM_NONZERO(a) for (; !(a)->chars[(a)->used - 1];
(a)->used--)
#define TRIM_AND_ZERO(a) do { TRIM(a); if (!(a)->used)
SET_SIGNUM(a, 0); } while (0)
+#define TRIM_AND_SIGN(a, s) do { TRIM(a); SET_SIGNUM(a, (a)->used ?
(s) : 0); } while (0
