[PATCH] pass constants as first argument to st_mult()

[PATCH] pass constants as first argument to st_mult()

[René Scharfe]

The result of st_mult() is the same no matter the order of its
arguments.  It invokes the macro unsigned_mult_overflows(), which
divides the second parameter by the first one.  Pass constants
first to allow that division to be done already at compile time.

Signed-off-by: Rene Scharfe <l.s.r@web.de>
---
 diffcore-rename.c | 2 +-
 refs.c            | 2 +-
 shallow.c         | 2 +-
 3 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/diffcore-rename.c b/diffcore-rename.c
index 58ac0a5..73d003a 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -541,7 +541,7 @@ void diffcore_rename(struct diff_options *options)
 				rename_dst_nr * rename_src_nr, 50, 1);
 	}
 
-	mx = xcalloc(st_mult(num_create, NUM_CANDIDATE_PER_DST), sizeof(*mx));
+	mx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_create), sizeof(*mx));
 	for (dst_cnt = i = 0; i < rename_dst_nr; i++) {
 		struct diff_filespec *two = rename_dst[i].two;
 		struct diff_score *m;
diff --git a/refs.c b/refs.c
index 814cad3..b4e7cac 100644
--- a/refs.c
+++ b/refs.c
@@ -922,7 +922,7 @@ char *shorten_unambiguous_ref(const char *refname, int strict)
 			/* -2 for strlen("%.*s") - strlen("%s"); +1 for NUL */
 			total_len += strlen(ref_rev_parse_rules[nr_rules]) - 2 + 1;
 
-		scanf_fmts = xmalloc(st_add(st_mult(nr_rules, sizeof(char *)), total_len));
+		scanf_fmts = xmalloc(st_add(st_mult(sizeof(char *), nr_rules), total_len));
 
 		offset = 0;
 		for (i = 0; i < nr_rules; i++) {
diff --git a/shallow.c b/shallow.c
index 4d554ca..54e2db7 100644
--- a/shallow.c
+++ b/shallow.c
@@ -389,7 +389,7 @@ static void paint_down(struct paint_info *info, const unsigned char *sha1,
 	unsigned int i, nr;
 	struct commit_list *head = NULL;
 	int bitmap_nr = (info->nr_bits + 31) / 32;
-	size_t bitmap_size = st_mult(bitmap_nr, sizeof(uint32_t));
+	size_t bitmap_size = st_mult(sizeof(uint32_t), bitmap_nr);
 	uint32_t *tmp = xmalloc(bitmap_size); /* to be freed before return */
 	uint32_t *bitmap = paint_alloc(info);
 	struct commit *c = lookup_commit_reference_gently(sha1, 1);
-- 
2.9.2

Re: [PATCH] pass constants as first argument to st_mult()

[Jeff King]

On Sat, Jul 30, 2016 at 08:18:31PM +0200, René Scharfe wrote:

> The result of st_mult() is the same no matter the order of its
> arguments.  It invokes the macro unsigned_mult_overflows(), which
> divides the second parameter by the first one.  Pass constants
> first to allow that division to be done already at compile time.

I'm not opposed to this, as it's easy to do (though I suspect new calls
may be introduced that violate it).

But if we really are worried about the performance of st_mult(), I
think:

  static inline size_t st_mult(size_t a, size_t b)
  {
	size_t result;
	if (!__builtin_mul_overflow(a, b, &result))
		die("whoops!");
	return result;
  }

is the right direction. I just haven't gotten around to producing a
polished patch.

> diff --git a/diffcore-rename.c b/diffcore-rename.c
> index 58ac0a5..73d003a 100644
> --- a/diffcore-rename.c
> +++ b/diffcore-rename.c
> @@ -541,7 +541,7 @@ void diffcore_rename(struct diff_options *options)
>  				rename_dst_nr * rename_src_nr, 50, 1);
>  	}
>  
> -	mx = xcalloc(st_mult(num_create, NUM_CANDIDATE_PER_DST), sizeof(*mx));
> +	mx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_create), sizeof(*mx));

I didn't look at all of the calls, but I wonder if it is a natural
pattern to put the constant second.  Since multiplication is
commutative, it would be correct for st_mult() to just flip the order of
arguments it feeds to unsigned_mult_overflows().

That may introduce the same inefficiency in other callsites, but I
wonder if it would be fewer.

-Peff

Re: [PATCH] pass constants as first argument to st_mult()

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

>> -	mx = xcalloc(st_mult(num_create, NUM_CANDIDATE_PER_DST), sizeof(*mx));
>> +	mx = xcalloc(st_mult(NUM_CANDIDATE_PER_DST, num_create), sizeof(*mx));
>
> I didn't look at all of the calls, but I wonder if it is a natural
> pattern to put the constant second.  

Between

    st_mult(GIT_SHA1_RAWSZ, i)
    st_mult(i, GIT_SHA1_RAWSZ)

the former is more intuitive at least to me [*1*], but calloc(3) disagrees
with me.

> Since multiplication is
> commutative, it would be correct for st_mult() to just flip the order of
> arguments it feeds to unsigned_mult_overflows().
>
> That may introduce the same inefficiency in other callsites, but I
> wonder if it would be fewer.

"git grep -A3 st_mult \*.c" seems to tell me that the callsites with
a constant in their first parameter are the majority (many are
sizeof(something)).  The three places in the patch under discussion
are the only places that got them in the different order.


[Footnote]

*1* I have a slight suspicion that this is cultural, i.e. how
arithmetic is taught in grade schools.  When an apple costs 30 yen
and I have 5 of them, I was taught to multiply 30x5 to arrive at
150, not 5x30=150, and I am guessing that is because the former
matches the natural order of these two numbers (cost, quantity) in
the language I was taught.

Re: [PATCH] pass constants as first argument to st_mult()

[Jeff King]

On Mon, Aug 01, 2016 at 02:00:46PM -0700, Junio C Hamano wrote:

> > Since multiplication is
> > commutative, it would be correct for st_mult() to just flip the order of
> > arguments it feeds to unsigned_mult_overflows().
> >
> > That may introduce the same inefficiency in other callsites, but I
> > wonder if it would be fewer.
> 
> "git grep -A3 st_mult \*.c" seems to tell me that the callsites with
> a constant in their first parameter are the majority (many are
> sizeof(something)).  The three places in the patch under discussion
> are the only places that got them in the different order.

Thanks for checking. I should have been less lazy and done it myself.
If the majority are the other way, I agree that just fixing the minority
is the best path forward.

> *1* I have a slight suspicion that this is cultural, i.e. how
> arithmetic is taught in grade schools.  When an apple costs 30 yen
> and I have 5 of them, I was taught to multiply 30x5 to arrive at
> 150, not 5x30=150, and I am guessing that is because the former
> matches the natural order of these two numbers (cost, quantity) in
> the language I was taught.

You might be right. I was trying to figure out what is "natural" for me
in these cases, but after thinking about it for 2 minutes, I'm pretty
sure anything resembling "natural" is lost as I try to out-think myself. :)

-Peff

Re: [PATCH] pass constants as first argument to st_mult()

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

>> *1* I have a slight suspicion that this is cultural, i.e. how
>> arithmetic is taught in grade schools.  When an apple costs 30 yen
>> and I have 5 of them, I was taught to multiply 30x5 to arrive at
>> 150, not 5x30=150, and I am guessing that is because the former
>> matches the natural order of these two numbers (cost, quantity) in
>> the language I was taught.
>
> You might be right. I was trying to figure out what is "natural" for me
> in these cases, but after thinking about it for 2 minutes, I'm pretty
> sure anything resembling "natural" is lost as I try to out-think myself. :)

Do native English speakers (or more in general Europeans) think of
the apple example more like "5 apples, 30 cents each", and do 5x30?

Re: [PATCH] pass constants as first argument to st_mult()

[Jeff King]

On Mon, Aug 01, 2016 at 03:31:45PM -0700, Junio C Hamano wrote:

> Jeff King <peff@peff.net> writes:
> 
> >> *1* I have a slight suspicion that this is cultural, i.e. how
> >> arithmetic is taught in grade schools.  When an apple costs 30 yen
> >> and I have 5 of them, I was taught to multiply 30x5 to arrive at
> >> 150, not 5x30=150, and I am guessing that is because the former
> >> matches the natural order of these two numbers (cost, quantity) in
> >> the language I was taught.
> >
> > You might be right. I was trying to figure out what is "natural" for me
> > in these cases, but after thinking about it for 2 minutes, I'm pretty
> > sure anything resembling "natural" is lost as I try to out-think myself. :)
> 
> Do native English speakers (or more in general Europeans) think of
> the apple example more like "5 apples, 30 cents each", and do 5x30?

I think in my head I rewrite any multiplication like "N of M" as having
"N" as the smaller number. I.e., it is conceptually simpler to me to
count five 30's, then 30 five's (even though I do not implement it in my
head as a sequence of additions, of course; I'd probably do that
particular case as "half of ten 30's").

I have no idea if that's cultural or not, though. I'm pretty sure "half
of ten 30's" was not taught in schools. All I remember of grade school
multiplication is them insisting we write down all of our steps, no
matter how trivial the problem would be to do in our heads. :)

-Peff

Re: [PATCH] pass constants as first argument to st_mult()

[Junio C Hamano]

On Wed, Aug 3, 2016 at 12:13 PM, Jeff King <peff@peff.net> wrote:
> On Mon, Aug 01, 2016 at 03:31:45PM -0700, Junio C Hamano wrote:
>
> I think in my head I rewrite any multiplication like "N of M" as having
> "N" as the smaller number. I.e., it is conceptually simpler to me to
> count five 30's, then 30 five's (even though I do not implement it in my
> head as a sequence of additions, of course; I'd probably do that
> particular case as "half of ten 30's").
>
> I have no idea if that's cultural or not, though.

Now, when you say "count five 30's", which one do you have
in mind? 5x30, or 30x5?

If you meant the former, I think that _is_ cultural. I am pretty
sure that I was taught in school(s) to read 5x30 as adding 5
thirty times.

Re: [PATCH] pass constants as first argument to st_mult()

[Jeff King]

On Wed, Aug 03, 2016 at 12:41:30PM -0700, Junio C Hamano wrote:

> On Wed, Aug 3, 2016 at 12:13 PM, Jeff King <peff@peff.net> wrote:
> > On Mon, Aug 01, 2016 at 03:31:45PM -0700, Junio C Hamano wrote:
> >
> > I think in my head I rewrite any multiplication like "N of M" as having
> > "N" as the smaller number. I.e., it is conceptually simpler to me to
> > count five 30's, then 30 five's (even though I do not implement it in my
> > head as a sequence of additions, of course; I'd probably do that
> > particular case as "half of ten 30's").
> >
> > I have no idea if that's cultural or not, though.
> 
> Now, when you say "count five 30's", which one do you have
> in mind? 5x30, or 30x5?
> 
> If you meant the former, I think that _is_ cultural. I am pretty
> sure that I was taught in school(s) to read 5x30 as adding 5
> thirty times.

I think I would say "30x5" in that case. But I'm not sure where that
comes from, and I'm not even 100% sure that I would say that (after
thinking about it, it's hard for me to figure out what I would have done
if I _hadn't_ just thought about it).

-Peff

Re: [PATCH] pass constants as first argument to st_mult()

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Wed, Aug 03, 2016 at 12:41:30PM -0700, Junio C Hamano wrote:
>
>> On Wed, Aug 3, 2016 at 12:13 PM, Jeff King <peff@peff.net> wrote:
>> > On Mon, Aug 01, 2016 at 03:31:45PM -0700, Junio C Hamano wrote:
>> >
>> > I think in my head I rewrite any multiplication like "N of M" as having
>> > "N" as the smaller number. I.e., it is conceptually simpler to me to
>> > count five 30's, then 30 five's (even though I do not implement it in my
>> > head as a sequence of additions, of course; I'd probably do that
>> > particular case as "half of ten 30's").
>> >
>> > I have no idea if that's cultural or not, though.
>> 
>> Now, when you say "count five 30's", which one do you have
>> in mind? 5x30, or 30x5?
>> 
>> If you meant the former, I think that _is_ cultural. I am pretty
>> sure that I was taught in school(s) to read 5x30 as adding 5
>> thirty times.
>
> I think I would say "30x5" in that case. But I'm not sure where that
> comes from, and I'm not even 100% sure that I would say that (after
> thinking about it, it's hard for me to figure out what I would have done
> if I _hadn't_ just thought about it).

By the way, reading "30x5" as "count five 30's" disagrees with
calloc(nmemb=5, size=30), which wants to add 30-byte necessary for
each member 5 times to allocate 150 bytes.

Anyway, this tangent is long enough ;-)

Re: [PATCH] pass constants as first argument to st_mult()

[Stefan Beller]

On Wed, Aug 3, 2016 at 12:49 PM, Jeff King <peff@peff.net> wrote:
> On Wed, Aug 03, 2016 at 12:41:30PM -0700, Junio C Hamano wrote:
>
>> On Wed, Aug 3, 2016 at 12:13 PM, Jeff King <peff@peff.net> wrote:
>> > On Mon, Aug 01, 2016 at 03:31:45PM -0700, Junio C Hamano wrote:
>> >
>> > I think in my head I rewrite any multiplication like "N of M" as having
>> > "N" as the smaller number. I.e., it is conceptually simpler to me to
>> > count five 30's, then 30 five's (even though I do not implement it in my
>> > head as a sequence of additions, of course; I'd probably do that
>> > particular case as "half of ten 30's").
>> >
>> > I have no idea if that's cultural or not, though.

Well I think there is a difference between how you do the math in your head
and between the textbook question.

In textbook I would expect 5x30, because first we need to talk about the
object before the price of the object makes sense:
"I am interested in 5 apples, and each apple costs 30 yen, so I am paying
150 yen". Only that in Europe you would substitute the 30 by 0.84 Euros
(integer-> number with 2 values after comma, not quite a float).

When doing the math in your head you look for the easy tricks, i.e.
x5  = x10 /2 or such.

I think I'd find calloc intuitive as a typical textbook question, "I
want to have
space for "foos", which each cost 5 memory, go figure out how much I need
and hand it back to me".

Re: [PATCH] pass constants as first argument to st_mult()

[Jeff King]

On Wed, Aug 03, 2016 at 12:59:34PM -0700, Stefan Beller wrote:

> I think I'd find calloc intuitive as a typical textbook question, "I
> want to have space for "foos", which each cost 5 memory, go figure out
> how much I need and hand it back to me".

I think it is more a language question than a math one, though. Is it "5
instances, costing 30 each" or "30-cost instances, 5 times". They are
the same semantically (there is no "30 instances of a 5-cost thing",
which does not map to the problem space), but just with a different
order.

-Peff

Re: [PATCH] pass constants as first argument to st_mult()

[Christian Couder]

On Wed, Aug 3, 2016 at 9:13 PM, Jeff King <peff@peff.net> wrote:
> On Mon, Aug 01, 2016 at 03:31:45PM -0700, Junio C Hamano wrote:
>
>> Jeff King <peff@peff.net> writes:
>>
>> >> *1* I have a slight suspicion that this is cultural, i.e. how
>> >> arithmetic is taught in grade schools.  When an apple costs 30 yen
>> >> and I have 5 of them, I was taught to multiply 30x5 to arrive at
>> >> 150, not 5x30=150, and I am guessing that is because the former
>> >> matches the natural order of these two numbers (cost, quantity) in
>> >> the language I was taught.
>> >
>> > You might be right. I was trying to figure out what is "natural" for me
>> > in these cases, but after thinking about it for 2 minutes, I'm pretty
>> > sure anything resembling "natural" is lost as I try to out-think myself. :)
>>
>> Do native English speakers (or more in general Europeans) think of
>> the apple example more like "5 apples, 30 cents each", and do 5x30?
>
> I think in my head I rewrite any multiplication like "N of M" as having
> "N" as the smaller number. I.e., it is conceptually simpler to me to
> count five 30's, then 30 five's (even though I do not implement it in my
> head as a sequence of additions, of course; I'd probably do that
> particular case as "half of ten 30's").
>
> I have no idea if that's cultural or not, though. I'm pretty sure "half
> of ten 30's" was not taught in schools. All I remember of grade school
> multiplication is them insisting we write down all of our steps, no
> matter how trivial the problem would be to do in our heads. :)

Yeah, I would be tempted to write all the steps too like this:

"An apple costs 30 yen and I have 5 of them" means:

Cost(1 apple) = 30 cents
Cost(5 apples) = 5 * Cost(1 apple) = 5 * 30 cents = 150 cents

so it would be more "5x30=150" than "30x5" in this case for me.