Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <796e366e-f321-25a3-78e7-8a3800e62eeb@davidgf.es>
Date: Sun, 26 Nov 2017 01:49:09 +0100
From: David Guillen Fandos <david@...idgf.es>
To: musl@...ts.openwall.com
Subject: Re: Do not use 64 bit division if possible

Hey,

Wow that's an awesome optimization (the a&-a), didn't know gcc was smart 
enough to figure that out by itself :D
I just realized that PAGE_SIZE seems indeed to be defined to a constant 
for some architectures, did not notice since I was running on MIPS which 
has a page size different for each uarch.

I'd say the (a&-a) is a very simple optimization and we should use it, 
since it adds almost no complexity and sames some cycles and some .text 
bytes, which is sometimes a bit tight.

Something like this? Doesn't hurt constants, improves some arches :)

diff --git a/src/conf/sysconf.c b/src/conf/sysconf.c
index b8b761d0..aa9fc9d1 100644
--- a/src/conf/sysconf.c
+++ b/src/conf/sysconf.c
@@ -206,7 +206,7 @@ long sysconf(int name)
		if (name==_SC_PHYS_PAGES) mem = si.totalram;
		else mem = si.freeram + si.bufferram;
		mem *= si.mem_unit;
-		mem /= PAGE_SIZE;
+		mem /= (unsigned)(PAGE_SIZE & -PAGE_SIZE);
		return (mem > LONG_MAX) ? LONG_MAX : mem;
		case JT_ZERO & 255:
		return 0;

On 26/11/17 01:10, Michael Clark wrote:
> 
> 
>> On 26/11/2017, at 12:53 PM, Rich Felker <dalias@...c.org> wrote:
>>
>> On Sun, Nov 26, 2017 at 12:46:56AM +0100, David Guillen Fandos wrote:
>>> Thanks for your response.
>>> Please note that PAGE_SIZE is not a constant but an alias to
>>> libc.page_size which is a variable of type size_t (signed).
>>> That's why at O1+ gcc doesn't generate a shift.
>>
>> Indeed; this varies by arch.
> 
> Oh, I wasn’t aware of that.
> 
>>> I also created a patch to include libc.page_shift, but as far as I
>>> can see no other functions would benefit from it, since there's no
>>> other divides there (only negations, additions and subtractions).
>>
>> Adding infrastructure complexity except in cases where it makes a
>> significant improvement to size or performance is generally not
>> desirable. mmap() is one other place where, in principle, division by
>> PAGE_SIZE might take place, but in practice the size is constant 4096
>> or 8192 on all archs.
>>
>>> And yeah I agree, a_ctz_l is not exactly inexpensive but I guess it
>>> is better than full 64 bit signed division (that's why I cast
>>> unsigned otherwise the shift right is not trivial due to the sign).
>>
>> The cost here is more a matter of adding a reading complexity
>> dependency on musl internals (a_*) where it's not needed. I wonder if
>> GCC could optimize it if we instead of /PAGE_SIZE wrote
>> /(PAGE_SIZE&-PAGE_SIZE). Or if we did something like define PAGE_SIZE
>> as ((libc.page_size&-libc.page_size)==libc.page_size ? libc.page_size
>> : 1/0) so that "PAGE_SIZE is not a power of 2" would become an
>> unreachable case.
> 
> Interesting. It seems GCC figures out the division by zero is unreachable but the (n&-n) expression leads to a power of two, not to a  log2 n so the ctz is still required.
> 
> - https://cx.rv8.io/g/eHf2Ah
> 
>   One could do so once at initialisation time and add PAGE_SHIFT and on architectures with variable page sizes do this:
> 
> #define PAGE_SHIFT libc.page_shift
> 
> diff --git a/src/env/__libc_start_main.c b/src/env/__libc_start_main.c
> index 2d758af..f24d10a 100644
> --- a/src/env/__libc_start_main.c
> +++ b/src/env/__libc_start_main.c
> @@ -29,6 +29,7 @@ void __init_libc(char **envp, char *pn)
>          __hwcap = aux[AT_HWCAP];
>          __sysinfo = aux[AT_SYSINFO];
>          libc.page_size = aux[AT_PAGESZ];
> +       libc.page_shift = a_ctz_l(libc.page_size);
>   
>          if (!pn) pn = (void*)aux[AT_EXECFN];
>          if (!pn) pn = "";
> 
> That isolates the a_ctz_l to one place.
> 

Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.