pass constants as first argument to st_mult()
PATCH 1/1 pass constants as first argument to st_mult()
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.
--- diffcore-rename.c | 2 +- refs.c | 2 +- shallow.c | 2 +- 3 files changed, 3 insertions(+), 3 deletions(-)
diffcore-rename.c +1 -1
@@ -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;
refs.c +1 -1
@@ -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++) {
shallow.c +1 -1
@@ -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 );
Signature · 1 line
2.9.2
Quoted 4 lines · René Scharfe
The result of
st_mult()is the same no matter the order of its arguments. It invokes the macrounsigned_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.
diffcore-rename.c void diffcore_rename(struct diff_options *options) · line 544
Quoted 10 lines
diffcore-rename.c +1
-1@@ -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
Quoted 5 lines · Jeff King
diffcore-rename.c void diffcore_rename(struct diff_options *options) · line 544
Quoted 2 lines
diffcore-rename.c +1
-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.
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.
Quoted 6 lines
Since multiplication is
commutative, it would be correct forst_mult()to just flip the order of arguments it feeds tounsigned_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.
Quoted 11 lines · Junio C Hamano
Quoted 6 lines
Since multiplication is
commutative, it would be correct forst_mult()to just flip the order of arguments it feeds tounsigned_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.
Quoted 6 lines
*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
Quoted 10 lines · Jeff King
Quoted 6 lines
*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?
Quoted 9 lines · Junio C Hamano
Quoted 7 lines · Jeff King
Quoted 6 lines
*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.
Quoted 6 lines
Quoted 3 lines
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
Quoted 9 lines · Jeff King
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.
Quoted 9 lines · Junio C Hamano
Quoted 8 lines · Jeff King
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").
Quoted 8 lines
Quoted 1 line
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
Quoted 16 lines · Jeff King
Quoted 14 lines · Junio C Hamano
Quoted 9 lines · Jeff King
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?
Quoted 8 lines
Quoted 3 lines
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 ;-)
Quoted 5 lines · Jeff King
Quoted 3 lines · Junio C Hamano
Quoted 2 lines · Jeff King
On Mon, Aug 01, 2016 at 03:31:45PM -0700, Junio C Hamano wrote:
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
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".
Quoted 3 lines · Stefan Beller
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
Quoted 24 lines · Jeff King
Quoted 9 lines · Junio C Hamano
Quoted 7 lines · Jeff King
Quoted 6 lines
*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.
Quoted 6 lines
Quoted 3 lines
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").
Quoted 4 lines
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.