Re: 0 is not a power of 2
Aren't predictable branches cheap on current architectures?
Atila
On Tuesday, 19 May 2015 at 05:16:48 UTC, Andrei Alexandrescu
wrote:
So there's this classic trick:
bool isPowerOf2(uint x)
{
return (x & (x - 1)) == 0;
}
Pretty neat, but it wrongly returns true for x == 0. So the
obvious fix is:
bool isPowerOf2(uint x)
{
return x && (x & (x - 1)) == 0;
}
But that has branches in it. So I came up with:
bool isPowerOf2(uint x)
{
return (x & (x - 1) | !x) == 0;
}
which has no branches at least with dmd, see
http://goo.gl/TVkCwc.
Any ideas for faster code?
Thanks,
Andrei
Re: 0 is not a power of 2
On Tuesday, 19 May 2015 at 05:16:48 UTC, Andrei Alexandrescu
wrote:
So there's this classic trick:
bool isPowerOf2(uint x)
{
return (x & (x - 1)) == 0;
}
Pretty neat, but it wrongly returns true for x == 0. So the
obvious fix is:
bool isPowerOf2(uint x)
{
return x && (x & (x - 1)) == 0;
}
But that has branches in it. So I came up with:
bool isPowerOf2(uint x)
{
return (x & (x - 1) | !x) == 0;
}
which has no branches at least with dmd, see
http://goo.gl/TVkCwc.
Any ideas for faster code?
Thanks,
Andrei
I tested with a few different (modern) backends to see what was
generated, they all essentially give you this (gcc 5.1.0 -O3
-march=broadwell):
isPowerOf2:
xorl%eax, %eax
testl %edi, %edi
je .L5
blsr%edi, %edi
testl %edi, %edi
sete%al
.L5:
ret
isPowerOf2b:
blsr%edi, %edx
xorl%eax, %eax
testl %edi, %edi
sete%al
orl %eax, %edx
sete%al
ret
but if your not restricting the build to such recent processor,
you can't emit BLSR, so you get this instead (gcc 5.1.0 -O3):
isPowerOf2b:
leal-1(%rdi), %eax
xorl%edx, %edx
andl%edi, %eax
testl %edi, %edi
sete%dl
orl %edx, %eax
sete%al
ret
Re: 0 is not a power of 2
On Tuesday, 19 May 2015 at 05:16:48 UTC, Andrei Alexandrescu
wrote:
So there's this classic trick:
bool isPowerOf2(uint x)
{
return (x & (x - 1)) == 0;
}
which has no branches at least with dmd, see
http://goo.gl/TVkCwc.
Any ideas for faster code?
If you dont mind asm then after you do...
tmp = x-1;
you could add the borrow/carry flag back onto the tmp, so it'd
add back up to zero any time there's an underflow in the (x-1) op.
So two extra instructions, (you need a zero for the ADC) no
branch.
Re: 0 is not a power of 2
On Tuesday, 19 May 2015 at 07:56:27 UTC, Atila Neves wrote: Aren't predictable branches cheap on current architectures? Yes they are, and it seems one would rarely if ever call isPowOf2 with 0 in std.allocator. A good thing to do, is to use a good hardware event profiler like perf, and record the branch misses. Perf is also the right tool to compare the branchless version (I doubt it's significantly better, especially since the felt of the 0 branch is just a constant).
Re: [Request for ABI Breakage]: Ambiguity between extern(Pascal) vs. Template Value Parameters.
"Steven Schveighoffer" wrote in message news:mjdgdk$15c4$1...@digitalmars.com... I meant call it something else, so it's not confused with the original meaning of extern(Pascal). If you decided to limit it to only Windows API or similar functions. It's not used for the Windows API, it _was_ used for the Windows API. The current calling convention is extern(Windows) which is IIRC the same thing with the argument push order reversed. It might still survive in a few dark corners, not sure.
Re: [dlang website] Up Arrow in library
On Monday, 18 May 2015 at 19:22:09 UTC, Walter Bright wrote: On 5/18/2015 2:18 AM, Chris wrote: A small suggestion for the library layout (phobos etc) on dlang.org: An up arrow like on duckduckgo would be cool, i.e. as soon as you scroll down an up arrow appears that brings you back to the top, if you click on it. This would be very convenient when browsing through the library. Would it be hard to add this feature? If needs be, I could write a JS function for that. Pressing the [Home] key does that. And what do you use on touch screen devices? The up arrow (on duckduckgo for example) is very convenient. It's one of those little things that are not _strictly_ necessary but often come in handy. I agree that a "back to top" link under every function would be kinda stupid. But a little arrow that resides unobtrusively in the corner of the browser window does no harm.
Re: 0 is not a power of 2
I believe you can also do x & -x == x. I'm not sure if that will
be actually faster or slower. You could maybe cut the
instructions down a little with an asm{} block. The compiler
might not figure out that it can re-use a register for x on the
left and x on the right there. You might use popcnt in a
version() block too, so you can use the instruction when you've
got it.
Re: Let's improve D's exceptions
For me it feels like until the issue with non-allocating exception instances on their own is solved, everything else doesn't make that much of a difference. (I use enforce a lot)
Re: 0 is not a power of 2
On Tuesday, 19 May 2015 at 09:34:04 UTC, Almighty Bob wrote:
On Tuesday, 19 May 2015 at 05:16:48 UTC, Andrei Alexandrescu
wrote:
So there's this classic trick:
bool isPowerOf2(uint x)
{
return (x & (x - 1)) == 0;
}
which has no branches at least with dmd, see
http://goo.gl/TVkCwc.
Any ideas for faster code?
If you dont mind asm then after you do...
tmp = x-1;
you could add the borrow/carry flag back onto the tmp, so it'd
add back up to zero any time there's an underflow in the (x-1)
op.
So two extra instructions, (you need a zero for the ADC) no
branch.
Oops, should be either add the carry onto x, or subtract the
carry from tmp. Either way the result of the & is non zero.
Re: 0 is not a power of 2
On Tuesday, 19 May 2015 at 10:59:53 UTC, w0rp wrote: I believe you can also do x & -x == x. I think that still returns true for x = 0.
Re: Any plans to support STL value types?
JMD is right. Using inheritance for value types is a bad idea, and it shouldn't be done. The problem is that when you assign a derived value type to a base value type, the members in the derived type are removed, and this can lead to very weird behaviour. You could enforce that derived value types can never add any members, but then what would be the point? For adding virtual method calls for changing behaviour? Using inheritance for reference types only was one of the better design decisions for D. If you want to treat a set of structs in a similar way, you can do it better with parametric polymorphism than with classes and virtual method calls.
Re: 0 is not a power of 2
On Tuesday, 19 May 2015 at 12:00:30 UTC, Almighty Bob wrote: On Tuesday, 19 May 2015 at 10:59:53 UTC, w0rp wrote: I believe you can also do x & -x == x. I think that still returns true for x = 0. You are right. Disregard that.
Re: 0 is not a power of 2
On Tuesday, 19 May 2015 at 05:16:48 UTC, Andrei Alexandrescu wrote: ... Any ideas for faster code? Thanks, Andrei I found www.davespace.co.uk/blog/20150131-branchless-sequences.html and its links to be useful and interesting. Nic
Re: Request for Features/Ideas: A std.archive package
On Sunday, 17 May 2015 at 16:32:31 UTC, Liam McSherry wrote: Phobos currently has packages for working with various archives (Zlib/Gzip, Zip), and it's probably reasonable to expect that support for more archive formats will be added in future. Before any more are added, it would probably be beneficial to define an interface that any modules adding support for archives should obey, and having archive related modules under std.archive for organisational purposes probably wouldn't hurt. I saw a suggestion for improved archive support on the D wiki's wish list, and the code link 'std.archive' module in the review queue now 404s, so it looks to be the case that there isn't currently an effort to implement an archiving package for Phobos. What I would propose for such a package is: - Split archives in to two categories: stream-based (Gzip, Zlib, Bzip, etc) and file-based (Zip, Tar). - Make support for creating archives optional (e.g. by having IStreamArchive and IWritableStreamArchive). - Make compression-related functionality separate (e.g. through an ICompressableArchive(T) interface, where T is an enum specifying algorithms). I'm not sure on this one, so ideas are especially welcome for it. - A hierarchy of exceptions for implementations under std.archive rather than the current Phobos norm of everything having its own exceptions. I'd like to know whether there would be demand for such a package, and what the community would want in terms of the API and features. I haven't yet written any code for the package as the API is going to be one of the most important parts, and I thought it would be best to have agreement on what is wanted before starting on it. We need two things actually: 1) compress package with set of commonly used compression algorithms. std.alg.compress comes to mind as package name. 2) VFS module/package with set of interfaces and reference implementations for as many formats as possible. 3) It would be extremely useful to have something like Java SPI (http://en.wikipedia.org/wiki/Service_provider_interface) in D. All the VFS implementations would then follow this standard and give us truly runtime-replaceable components. More about this: http://resources.sei.cmu.edu/asset_files/TechnicalNote/2002_004_001_13958.pdf
Re: 0 is not a power of 2
On 5/19/15 1:37 AM, H. S. Teoh via Digitalmars-d wrote:
On Mon, May 18, 2015 at 10:16:47PM -0700, Andrei Alexandrescu via Digitalmars-d
wrote:
[...]
bool isPowerOf2(uint x)
{
return (x & (x - 1) | !x) == 0;
}
[...]
Are you sure that's correct? Doesn't that return true for all non-zero
numbers?
It's bitwise or, not logic or.
-Steve
Re: Any plans to support STL value types?
On Friday, 15 May 2015 at 19:51:09 UTC, anonymous wrote: On Friday, 15 May 2015 at 19:44:29 UTC, Jonathan M Davis wrote: On Friday, 15 May 2015 at 18:42:31 UTC, Kagamin wrote: Many STL types inherit from base classes, yet they are used as value types: std::string, std::vector etc. Are there plans to support C++ types with inheritance as proper value types in D frontend? Given that the inheritance they have is actually undesirable when they are treated as value types, I doubt that there's much need. If you're using inheritance in C++, you're putting your class on the heap and accessing it via pointers, in which case, accessing them in D as classes makes sense. And if you're using these STL types as value types on the stack, then they can be treated as value types. Doing otherwise just risks object slicing, which is not desirable in the least. So, while I don't know how we're going to be handling STL types (I don't even know what the current state of C++ state support is, since it keeps improving), I really don't see why there's value in supported inheritance with value types. It would just be begging for bugs - which is why native D types don't support it. - Jonathan M Davis rust does it just fine without slicing, and supports both static dispatch and dynamic dispatch through the same interface. http://blog.rust-lang.org/2015/05/11/traits.html honestly, this is one of the worst parts of D. Being forced to code a certain way because it might be misused is the equivalent of digital socialism. How is this a "digital socialism"? :) Nobody forces you anything. The community made Phobos - if you do not like it, use something else. :) There is Tango/D2 project too, if that one does not fit your need, use OR create something else! Second, what do you mean when you say (type) "D"? D community, D programming language, or what? If by D you refer to D as a programming language (and that is what I think when you say D) - sorry to break it up to you, but EVERY SINGLE language (not just programming) forces specific rules upon programmer! Back to the topic - nobody stops anyone from writing a module which provides what the original question was about. Is there any value in having STL value types? - I do not see them, but that does not mean someone else may see it differently.
Re: 0 is not a power of 2
On 5/19/15 1:16 AM, Andrei Alexandrescu wrote:
So there's this classic trick:
bool isPowerOf2(uint x)
{
return (x & (x - 1)) == 0;
}
Pretty neat, but it wrongly returns true for x == 0. So the obvious fix is:
bool isPowerOf2(uint x)
{
return x && (x & (x - 1)) == 0;
}
But that has branches in it. So I came up with:
bool isPowerOf2(uint x)
{
return (x & (x - 1) | !x) == 0;
}
which has no branches at least with dmd, see http://goo.gl/TVkCwc.
Is it just me, or is it odd that your first version generates xor and a
bunch of jumps?
I don't see xor anywhere in the "fast" version.
Another possibility is to avoid the zero check altogether. There may be
cases where you already know before calling isPowerOf2 that it's not
zero, and checking for zero again is wasteful.
Note that bsr is undefined for 0, so there is precedent for this.
-Steve
Re: Any plans to support STL value types?
On Tuesday, 19 May 2015 at 12:46:50 UTC, Dejan Lekic wrote: Is there any value in having STL value types? More natural and safe C++ interfacing instead of some bug-prone hybrid, which is neither D nor C++ and is even more horrible than C++ itself.
Re: 0 is not a power of 2
On 5/19/15 8:46 AM, Steven Schveighoffer wrote:
On 5/19/15 1:16 AM, Andrei Alexandrescu wrote:
So there's this classic trick:
bool isPowerOf2(uint x)
{
return (x & (x - 1)) == 0;
}
Pretty neat, but it wrongly returns true for x == 0. So the obvious
fix is:
bool isPowerOf2(uint x)
{
return x && (x & (x - 1)) == 0;
}
But that has branches in it. So I came up with:
bool isPowerOf2(uint x)
{
return (x & (x - 1) | !x) == 0;
}
which has no branches at least with dmd, see http://goo.gl/TVkCwc.
Is it just me, or is it odd that your first version generates xor and a
bunch of jumps?
I don't see xor anywhere in the "fast" version.
Nevermind, xor is just zeroing a register.
I will note though, changing the slow version to:
if(x) return (x & (x-1)) == 0;
return 0;
this reduces the jumps by 2.
-Steve
Re: 0 is not a power of 2
On Tuesday, 19 May 2015 at 05:16:48 UTC, Andrei Alexandrescu wrote: [...], but it wrongly returns true for x == 0. When we're talking about modulo 2^n arithmetic, 0 is in fact a power of two. Proof: 2^n mod 2^n == 0.
[dlang] Mistakes in documentation
I noticed some mistakes in http://dlang.org/regular-expression.html I haven't checked the whole page for mistakes, but I suggest we change the following paragraph: [Current] Here is where regular expressions come in handy, often succinctly called as regexes. Regexes are simple yet powerful language for defining patterns of strings, put together with a substitution mechanism, they form a Swiss Army knife of text processing. They are considered so useful that a number of languages provides built-in support for regular expressions. This does not nessary mean that built-in implies faster processing or more features. It's more a matter of providing convenient and friendly syntax for typical operations and usage patterns. [Suggestion] Here is where regular expressions – often just called regexes – come in handy. Regular expressions are a simple yet comprehensive language for defining string patterns. Combined with a mechanism for string substitution, regular expressions are a powerful tool for text processing. In fact, they are considered so useful that a number of languages provide built-in support for them. However, built-in support does not necessarily imply faster processing or more features, it is rather a way of providing a convenient and user-friendly syntax for typical operations and usage patterns. [something along these lines]
Re: Let's improve D's exceptions
On Monday, 18 May 2015 at 14:18:46 UTC, Steven Schveighoffer wrote: Alternatively, we could fix lazy parameters so they don't disable inlining (though the weight carried by enforce is so minor, I still don't think it's worth having). -Steve I disagree; I also heavily use enforce, and I find the overload that returns a value particularly useful for reducing indentation in my programs.
Re: Request for Features/Ideas: A std.archive package
On Tuesday, 19 May 2015 at 12:31:15 UTC, Dejan Lekic wrote: We need two things actually: 1) compress package with set of commonly used compression algorithms. std.alg.compress comes to mind as package name. A compression package would certainly be useful as the number of supported archives grows. 2) VFS module/package with set of interfaces and reference implementations for as many formats as possible. 3) It would be extremely useful to have something like Java SPI (http://en.wikipedia.org/wiki/Service_provider_interface) in D. All the VFS implementations would then follow this standard and give us truly runtime-replaceable components. More about this: http://resources.sei.cmu.edu/asset_files/TechnicalNote/2002_004_001_13958.pdf I imagine a VFS interface and an interface for file-based archives like Zip/Tar/7z would be fairly similar. Support for virtual filesystems could probably be implemented as part of the archive package. WRT runtime replaceability, the defining of a single set of exceptions (without making them too specific) for all std.archive submodules should help. The fact that there aren't any "standard" exceptions seems to come up a fair bit (DIP33, for example).
Re: [dlang] Mistakes in documentation
On Tue, May 19, 2015 at 01:43:13PM +, Chris via Digitalmars-d wrote: > I noticed some mistakes in > > http://dlang.org/regular-expression.html > > I haven't checked the whole page for mistakes, but I suggest we change the > following paragraph: > > [Current] > Here is where regular expressions come in handy, often succinctly called as > regexes. Regexes are simple yet powerful language for defining patterns of > strings, put together with a substitution mechanism, they form a Swiss Army > knife of text processing. They are considered so useful that a number of > languages provides built-in support for regular expressions. This does not > nessary mean that built-in implies faster processing or more features. It's > more a matter of providing convenient and friendly syntax for typical > operations and usage patterns. > > [Suggestion] > Here is where regular expressions – often just called regexes – come > in handy. Regular expressions are a simple yet comprehensive language for > defining string patterns. Combined with a mechanism for string substitution, > regular expressions are a powerful tool for text processing. In fact, they > are considered so useful that a number of languages provide built-in support > for them. However, built-in support does not necessarily imply > faster processing or more features, it is rather a way of providing a > convenient and user-friendly syntax for typical operations and usage > patterns. > > [something along these lines] Let's see the PR! ;-) T -- Philosophy: how to make a career out of daydreaming.
Re: 0 is not a power of 2
On 5/19/15 2:35 AM, Martin Nowak wrote: On Tuesday, 19 May 2015 at 07:56:27 UTC, Atila Neves wrote: Aren't predictable branches cheap on current architectures? Yes they are, and it seems one would rarely if ever call isPowOf2 with 0 in std.allocator. A good thing to do, is to use a good hardware event profiler like perf, and record the branch misses. Perf is also the right tool to compare the branchless version (I doubt it's significantly better, especially since the felt of the 0 branch is just a constant). Yah measuring on-line is clearly the way to go. A comment on the branches - the branch predictor has a limited capacity so branching here might take resources away from other places. -- Andrei
Re: [dlang] Mistakes in documentation
On Tuesday, 19 May 2015 at 14:29:10 UTC, H. S. Teoh wrote: On Tue, May 19, 2015 at 01:43:13PM +, Chris via Digitalmars-d wrote: I noticed some mistakes in http://dlang.org/regular-expression.html I haven't checked the whole page for mistakes, but I suggest we change the following paragraph: [Current] Here is where regular expressions come in handy, often succinctly called as regexes. Regexes are simple yet powerful language for defining patterns of strings, put together with a substitution mechanism, they form a Swiss Army knife of text processing. They are considered so useful that a number of languages provides built-in support for regular expressions. This does not nessary mean that built-in implies faster processing or more features. It's more a matter of providing convenient and friendly syntax for typical operations and usage patterns. [Suggestion] Here is where regular expressions – often just called regexes – come in handy. Regular expressions are a simple yet comprehensive language for defining string patterns. Combined with a mechanism for string substitution, regular expressions are a powerful tool for text processing. In fact, they are considered so useful that a number of languages provide built-in support for them. However, built-in support does not necessarily imply faster processing or more features, it is rather a way of providing a convenient and user-friendly syntax for typical operations and usage patterns. [something along these lines] Let's see the PR! ;-) T Can I pull it? I didn't know it was "pullable", else I would've pulled it already. (No pun in 10 did!)
Re: [dlang] Mistakes in documentation
On Tuesday, 19 May 2015 at 14:37:58 UTC, Chris wrote: Can I pull it? I didn't know it was "pullable", else I would've pulled it already. (No pun in 10 did!) The specific bit of documentation you were talking about is here: https://github.com/D-Programming-Language/phobos/blob/master/std/regex/package.d You'll need a GitHub account to pull the repo and file a PR.
Re: [dlang] Mistakes in documentation
On Tuesday, 19 May 2015 at 14:29:10 UTC, H. S. Teoh wrote: On Tue, May 19, 2015 at 01:43:13PM +, Chris via Digitalmars-d wrote: I noticed some mistakes in http://dlang.org/regular-expression.html I haven't checked the whole page for mistakes, but I suggest we change the following paragraph: [Current] Here is where regular expressions come in handy, often succinctly called as regexes. Regexes are simple yet powerful language for defining patterns of strings, put together with a substitution mechanism, they form a Swiss Army knife of text processing. They are considered so useful that a number of languages provides built-in support for regular expressions. This does not nessary mean that built-in implies faster processing or more features. It's more a matter of providing convenient and friendly syntax for typical operations and usage patterns. [Suggestion] Here is where regular expressions – often just called regexes – come in handy. Regular expressions are a simple yet comprehensive language for defining string patterns. Combined with a mechanism for string substitution, regular expressions are a powerful tool for text processing. In fact, they are considered so useful that a number of languages provide built-in support for them. However, built-in support does not necessarily imply faster processing or more features, it is rather a way of providing a convenient and user-friendly syntax for typical operations and usage patterns. [something along these lines] Let's see the PR! ;-) T Done. https://github.com/D-Programming-Language/dlang.org/pull/997
Re: 0 is not a power of 2
On Tuesday, 19 May 2015 at 08:28:11 UTC, John Colvin wrote: I tested with a few different (modern) backends to see what was generated, they all essentially give you this (gcc 5.1.0 -O3 -march=broadwell): isPowerOf2: xorl%eax, %eax testl %edi, %edi je .L5 blsr%edi, %edi testl %edi, %edi sete%al .L5: ret I think you used: return x && (x & (x - 1)) == 0; instead of return (x & (x - 1)) == 0 && x; Which influences code generation (more weight on the x == 0 test,) hence the branch.
Who's HTML-fu is strong?
Just submitted an enhancement request for formatting documentation of enumerations: https://issues.dlang.org/show_bug.cgi?id=14608 At least for the ddoc-based documentation, I think this is a CSS-only matter. Any takers? Thanks, Andrei
Re: Dconf Video / Projector Information
Aaand... late-breaking news from Chuck Allison himself: The screens are 1080p. We have 3 screens in the room, running simultaneously. No projector per se. Let’s do the insertion of the presentations. Our department can help pay for it if there aren’t enough funds from the registrations. I want to get as close as we can to the quality that Facebook has provided the last two years. I guess we'll owe him one. Andrei
Re: Dconf Video / Projector Information
On 5/18/15 5:04 PM, Brian Schott wrote: Will they be recording video from the laptop(s) in addition to a video camera in the room? I ask because giving a demo on a projector that's being captured by a camera is not a good experience for anybody watching the recording later. Info: Unfortunately, I don't know what the resolution of the projectors are. I don't think they are HD (1920x1080). As far as recording, we are currently scheduled to shoot single camera only in each room. There will not be any live switching between camera and computer for a stream. For an additional cost ($30/hr) we can insert someone's presentation in post if they leave us a copy. Andrei
Re: [dlang website] Up Arrow in library
"Chris" wrote: > On Monday, 18 May 2015 at 19:22:09 UTC, Walter Bright wrote: >> On 5/18/2015 2:18 AM, Chris wrote: >>> A small suggestion for the library layout (phobos etc) on >> dlang.org: >>> >>> An up arrow like on duckduckgo would be cool, i.e. as soon as >> you scroll >>> down an >>> up arrow appears that brings you back to the top, if you click >> on it. >>> This would >>> be very convenient when browsing through the library. Would it >> be hard >>> to add >>> this feature? If needs be, I could write a JS function for >> that. >> >> Pressing the [Home] key does that. > > And what do you use on touch screen devices? The up arrow (on duckduckgo > for example) is very convenient. It's one of those little things that are > not _strictly_ necessary but often come in handy. On iOS (Safari) just tap on the status bar at the top, where the time and battery status is displayed.
Re: 0 is not a power of 2
On Tuesday, 19 May 2015 at 05:51:27 UTC, Andrei Alexandrescu
wrote:
On 5/18/15 10:37 PM, H. S. Teoh via Digitalmars-d wrote:
On Mon, May 18, 2015 at 10:16:47PM -0700, Andrei Alexandrescu
via Digitalmars-d wrote:
[...]
bool isPowerOf2(uint x)
{
return (x & (x - 1) | !x) == 0;
}
[...]
Are you sure that's correct? Doesn't that return true for all
non-zero
numbers?
Excerpt from std.experimental.allocator.common:
package bool isPowerOf2(uint x)
{
return (x & (x - 1) | !x) == 0;
}
unittest
{
assert(!isPowerOf2(0));
assert(isPowerOf2(1));
assert(isPowerOf2(2));
assert(!isPowerOf2(3));
assert(isPowerOf2(4));
assert(!isPowerOf2(5));
assert(!isPowerOf2(6));
assert(!isPowerOf2(7));
assert(isPowerOf2(8));
assert(!isPowerOf2(9));
assert(!isPowerOf2(10));
}
I wish we had something like clang's -Wparenthesis.
I think
return ( (x & (x-1)) | !x ) == 0;
is much clearer here.
-Johan
Re: 0 is not a power of 2
Am Mon, 18 May 2015 22:16:47 -0700
schrieb Andrei Alexandrescu :
> But that has branches in it. So I came up with:
>
> bool isPowerOf2(uint x)
> {
> return (x & (x - 1) | !x) == 0;
> }
>
> which has no branches at least with dmd, see http://goo.gl/TVkCwc.
>
> Any ideas for faster code?
>
>
> Thanks,
>
> Andrei
Any faster ?! This is already minimal assembly code with
pretty looks!
While you are at it, you might also need "round pointer up to"
and "round pointer down to", which can be implemented with bit
ops for power-of-2 multiples.
Its the kind of stuff that's not really a std.algorithm
candidate, but still somewhat common in memory management code.
Often these and other little helpers end up in everyones
stdlib_extensions.d which I suppose don't look all that
different. Who has some of these in their code?:
- isPowerOf2, nextLargerPowerOf2
- roundUp/Down to multiple of X
- increment with wraparound at X
- clamp value (low, high or both ends)
- check if numerical value is in between two others
- compile time "iota"
- format an argument as it would appear in source code
(i.e. add quotes around strings)
--
Marco
Re: 0 is not a power of 2
On Tuesday, 19 May 2015 at 18:04:49 UTC, Marco Leise wrote:
Am Mon, 18 May 2015 22:16:47 -0700
schrieb Andrei Alexandrescu :
But that has branches in it. So I came up with:
bool isPowerOf2(uint x)
{
return (x & (x - 1) | !x) == 0;
}
which has no branches at least with dmd, see
http://goo.gl/TVkCwc.
Any ideas for faster code?
Thanks,
Andrei
Any faster ?! This is already minimal assembly code with
pretty looks!
While you are at it, you might also need "round pointer up to"
and "round pointer down to", which can be implemented with bit
ops for power-of-2 multiples.
Its the kind of stuff that's not really a std.algorithm
candidate, but still somewhat common in memory management code.
Often these and other little helpers end up in everyones
stdlib_extensions.d which I suppose don't look all that
different. Who has some of these in their code?:
- isPowerOf2, nextLargerPowerOf2
- roundUp/Down to multiple of X
- increment with wraparound at X
- clamp value (low, high or both ends)
- check if numerical value is in between two others
- compile time "iota"
- format an argument as it would appear in source code
(i.e. add quotes around strings)
+1 ;)
all except the last one
Re: 0 is not a power of 2
On Tuesday, 19 May 2015 at 15:39:16 UTC, safety0ff wrote: On Tuesday, 19 May 2015 at 08:28:11 UTC, John Colvin wrote: I tested with a few different (modern) backends to see what was generated, they all essentially give you this (gcc 5.1.0 -O3 -march=broadwell): isPowerOf2: xorl%eax, %eax testl %edi, %edi je .L5 blsr%edi, %edi testl %edi, %edi sete%al .L5: ret I think you used: return x && (x & (x - 1)) == 0; instead of return (x & (x - 1)) == 0 && x; Which influences code generation (more weight on the x == 0 test,) hence the branch. I used what andrei posted, but yes i do see the difference. How infuriating. A compiler that will entirely restructure your code leaving you with something unrecognisable in many cases, but in others is sensitive to the order of operands around an &&.
digitalmars-d@puremagic.com
I was wondering why T.init is treated as a manifest constant.
Don't all .init's end up in some data segment with a
resolvable address ?
In std.conv we have:
---
//emplace helper functions
private ref T emplaceInitializer(T)(ref T chunk) @trusted pure nothrow
{
static if (!hasElaborateAssign!T && isAssignable!T)
chunk = T.init;
else
{
import core.stdc.string : memcpy;
static immutable T init = T.init;
memcpy(&chunk, &init, T.sizeof);
}
return chunk;
}
---
It seems wasteful to create duplicates of .init, so it would
be nice if one could just write:
import core.stdc.string : memcpy;
memcpy(&chunk, &T.init, T.sizeof);
Likewise it would be nice to get the a class's .init[] slice
at compile-time.
--
Marco
digitalmars-d@puremagic.com
On Tuesday, 19 May 2015 at 18:39:43 UTC, Marco Leise wrote: I was wondering why T.init is treated as a manifest constant. Don't all .init's end up in some data segment with a resolvable address ? No, if the .init of a type is all zero bits then it is not placed in the data segment.
Re: Request for Features/Ideas: A std.archive package
On 2015-05-17 18:32, Liam McSherry wrote: Phobos currently has packages for working with various archives (Zlib/Gzip, Zip), and it's probably reasonable to expect that support for more archive formats will be added in future. Before any more are added, it would probably be beneficial to define an interface that any modules adding support for archives should obey, and having archive related modules under std.archive for organisational purposes probably wouldn't hurt. I saw a suggestion for improved archive support on the D wiki's wish list, and the code link 'std.archive' module in the review queue now 404s, so it looks to be the case that there isn't currently an effort to implement an archiving package for Phobos. What I would propose for such a package is: - Split archives in to two categories: stream-based (Gzip, Zlib, Bzip, etc) and file-based (Zip, Tar). - Make support for creating archives optional (e.g. by having IStreamArchive and IWritableStreamArchive). - Make compression-related functionality separate (e.g. through an ICompressableArchive(T) interface, where T is an enum specifying algorithms). I'm not sure on this one, so ideas are especially welcome for it. - A hierarchy of exceptions for implementations under std.archive rather than the current Phobos norm of everything having its own exceptions. I'd like to know whether there would be demand for such a package, and what the community would want in terms of the API and features. I haven't yet written any code for the package as the API is going to be one of the most important parts, and I thought it would be best to have agreement on what is wanted before starting on it. Support for RAR archives would be nice. -- /Jacob Carlborg
digitalmars-d@puremagic.com
On 5/19/15 2:40 PM, Marco Leise wrote:
I was wondering why T.init is treated as a manifest constant.
Don't all .init's end up in some data segment with a
resolvable address ?
Because T.init IS a manifest constant. In other words, doing:
T t = T.init;
Generates code to initialize t. It doesn't copy the data from some init
value stored in ROM.
Note, there is a place T.init is stored, and that is in typeid(T).init.
However, it's not always there (could be null if T.init is all zero).
What we could do, however, is make one copy of an addressable T.init:
template initialValue(T)
{
static immutable T initialValue = T.init;
}
that was used wherever it's needed, instead of creating a new one for
every time you need it.
Likewise it would be nice to get the a class's .init[] slice
at compile-time.
I think you can:
typeid(SomeClass).init
-Steve
Re: Who's HTML-fu is strong?
On Tuesday, 19 May 2015 at 16:14:29 UTC, Andrei Alexandrescu wrote: At least for the ddoc-based documentation, I think this is a CSS-only matter. Any takers? From a quick look, I think this will require changes in DMD Ddoc generation (to distinguish enums from other nested constructs), site .ddoc changes (to take advantage of the compiler changes and emit HTML tables instead of lists), and possibly CSS.
digitalmars-d@puremagic.com
> Likewise it would be nice to get the a class's .init[] slice > at compile-time. Scratch that part, the compile optimizes typeid(T).init.ptr down to a single load from a fixed address. That's pretty close to knowing and using it statically. -- Marco
Re: Request for Features/Ideas: A std.archive package
On Tuesday, 19 May 2015 at 18:46:34 UTC, Jacob Carlborg wrote: Support for RAR archives would be nice. It would be nice, but there isn't a great deal of documentation (publicly, at least). The RAR developers provide code for extracting it, but the licence forbids reverse engineering. At that point, it's murky water and down to law. For example, the UK's Copyright, Designs, and Patents Act allows reverse-engineering (and explicitly supersedes any licences), but only under certain conditons. The act states that decompilation/reverse-engineering is not allowed if you "[supply] the information obtained by the decompiling to any person to whom it is not necessary to supply it in order to achieve the permitted objective." Whether releasing D source code derived from a decompiled binary counts as "[supplying] to any person to whom it is not necessary..." is not something I'm qualified to determine. RARLAB have published technotes on the format, but I haven't read through them and it is possible that they don't give enough information. The technote on the RARLAB website also only seems to be for RAR 5.0, so supporting older versions could be an issue.
Re: 0 is not a power of 2
On 5/19/15 11:05 AM, Marco Leise wrote: While you are at it, you might also need "round pointer up to" and "round pointer down to", which can be implemented with bit ops for power-of-2 multiples. Yah, there are plenty of those in https://github.com/andralex/phobos/blob/allocator/std/experimental/allocator/common.d. Improvements welcome. -- Andrei
Re: 0 is not a power of 2
Have you tried things like : (x >> bsr(x)) == 1 ? I have no idea if this is faster or not, but worth trying.
Re: 0 is not a power of 2
On 5/19/15 4:01 PM, deadalnix wrote: Have you tried things like : (x >> bsr(x)) == 1 ? I have no idea if this is faster or not, but worth trying. Hm.. I think this would always succeed. Perhaps you mean: 1 << bsr(x) == x; And ironically, still doesn't work for 0 :D IIRC, bsr is a binary search (even when it's an instruction), I doubt it's as fast as subtraction and logic-and. -Steve
Re: Who's HTML-fu is strong?
On 5/19/15 11:57 AM, Vladimir Panteleev wrote: On Tuesday, 19 May 2015 at 16:14:29 UTC, Andrei Alexandrescu wrote: At least for the ddoc-based documentation, I think this is a CSS-only matter. Any takers? From a quick look, I think this will require changes in DMD Ddoc generation (to distinguish enums from other nested constructs), site .ddoc changes (to take advantage of the compiler changes and emit HTML tables instead of lists), and possibly CSS. I wonder whether a style can change an otherwise non-table tag to a table-like behavior. Here's the verbatim fragment generated for OpenRight (no broken lines at http://pasted.co/17dbcc83): $(DDOC_DECL $(DDOC_ANCHOR OpenRight)enum $(DDOC_PSYMBOL OpenRight): int; ) $(DDOC_DECL_DD $(DDOC_SECTIONS $(DDOC_SUMMARY Interval option specifier for $(D until) (below) and others.) ) $(DDOC_ENUM_MEMBERS $(DDOC_DECL $(DDOC_ANCHOR OpenRight.no)$(DDOC_PSYMBOL no)) $(DDOC_DECL_DD $(DDOC_SECTIONS $(DDOC_SUMMARY Interval is closed to the right (last element included)) ) ) $(DDOC_DECL $(DDOC_ANCHOR OpenRight.yes)$(DDOC_PSYMBOL yes)) $(DDOC_DECL_DD $(DDOC_SECTIONS $(DDOC_SUMMARY Interval is open to the right (last element is not included)) ) ) ) ) The challenge is defining DDOC_ENUM_MEMBERS (which right now is the same as DDOC_MEMBERS in such a way that achieves the better formatting. Andrei
Re: Who's HTML-fu is strong?
On Tuesday, 19 May 2015 at 20:07:09 UTC, Andrei Alexandrescu wrote: I wonder whether a style can change an otherwise non-table tag to a table-like behavior. Andrei It can, through the CSS "display" property: https://developer.mozilla.org/en-US/docs/Web/CSS/display#Values
Re: 0 is not a power of 2
On 05/19/2015 09:56 PM, Andrei Alexandrescu wrote:
On 5/19/15 11:05 AM, Marco Leise wrote:
While you are at it, you might also need "round pointer up to"
and "round pointer down to", which can be implemented with bit
ops for power-of-2 multiples.
Yah, there are plenty of those in
https://github.com/andralex/phobos/blob/allocator/std/experimental/allocator/common.d.
Improvements welcome. -- Andrei
In case the range of s is such that divideRoundUp is actually good
enough, the following avoids the conditional:
size_t roundUpToMultipleOf(size_t s,uint base){
auto t=s+base-1;
return t-t%base;
}
However, both divideRoundUp and this implementation of
roundUpToMultipleOf do not work for s in [size_t.max-base+2, size_t.max].
Re: 0 is not a power of 2
On Tuesday, 19 May 2015 at 20:01:29 UTC, deadalnix wrote: Have you tried things like : (x >> bsr(x)) == 1 ? I have no idea if this is faster or not, but worth trying. https://issues.dlang.org/show_bug.cgi?id=14380 "If the content source operand is 0, the content of the destination operand is undefined" - This applies to both the bsf and bsr instructions.
Re: 0 is not a power of 2
I think you can make the over/underflow at zero work in your
favor:
bool isPowerOf2(uint x)
{
return (x & -x) > (x - 1);
}
Re: 0 is not a power of 2
On Tuesday, 19 May 2015 at 20:41:58 UTC, Brian Schott wrote: On Tuesday, 19 May 2015 at 20:01:29 UTC, deadalnix wrote: Have you tried things like : (x >> bsr(x)) == 1 ? I have no idea if this is faster or not, but worth trying. https://issues.dlang.org/show_bug.cgi?id=14380 "If the content source operand is 0, the content of the destination operand is undefined" - This applies to both the bsf and bsr instructions. Why ain't we generating a tzcnt ?
Re: 0 is not a power of 2
On Tuesday, 19 May 2015 at 20:09:23 UTC, Steven Schveighoffer wrote: On 5/19/15 4:01 PM, deadalnix wrote: Have you tried things like : (x >> bsr(x)) == 1 ? I have no idea if this is faster or not, but worth trying. Hm.. I think this would always succeed. Perhaps you mean: 1 << bsr(x) == x; Both work as long as you use a fully defined instruction, like tzcnt.
Re: 0 is not a power of 2
On 5/19/15 5:32 PM, deadalnix wrote: On Tuesday, 19 May 2015 at 20:09:23 UTC, Steven Schveighoffer wrote: On 5/19/15 4:01 PM, deadalnix wrote: Have you tried things like : (x >> bsr(x)) == 1 ? I have no idea if this is faster or not, but worth trying. Hm.. I think this would always succeed. Perhaps you mean: 1 << bsr(x) == x; Both work as long as you use a fully defined instruction, like tzcnt. Hm... I messed up, (x >> bsr(x)) is always zero. I think you meant to write: x >> (bsr(x) - 1) which always is 1. Either way, it doesn't work. -Steve
Re: 0 is not a power of 2
On Tuesday, 19 May 2015 at 22:43:46 UTC, Steven Schveighoffer wrote: On 5/19/15 5:32 PM, deadalnix wrote: On Tuesday, 19 May 2015 at 20:09:23 UTC, Steven Schveighoffer wrote: On 5/19/15 4:01 PM, deadalnix wrote: Have you tried things like : (x >> bsr(x)) == 1 ? I have no idea if this is faster or not, but worth trying. Hm.. I think this would always succeed. Perhaps you mean: 1 << bsr(x) == x; Both work as long as you use a fully defined instruction, like tzcnt. Hm... I messed up, (x >> bsr(x)) is always zero. I think you meant to write: x >> (bsr(x) - 1) which always is 1. Either way, it doesn't work. -Steve No. bsr(1) is 0. 1 >> bsr(1) is 1. 0 >> anything is 0. So it doesn't matter if bsr is defined or not for 0.
digitalmars-d@puremagic.com
Am Tue, 19 May 2015 14:52:46 -0400
schrieb Steven Schveighoffer :
> On 5/19/15 2:40 PM, Marco Leise wrote:
> > I was wondering why T.init is treated as a manifest constant.
> > Don't all .init's end up in some data segment with a
> > resolvable address ?
>
> Because T.init IS a manifest constant. In other words, doing:
>
> T t = T.init;
>
> Generates code to initialize t. It doesn't copy the data from some init
> value stored in ROM.
Mhm. That allows the compiler optimize around "holes" (skip `=
void` initializers). But still, while it doesn't copy from
ROM, TypeInfo.init is mostly not-null, so there is still .init
copy placed in ROM that we just cannot access from D code!
> Note, there is a place T.init is stored, and that is in typeid(T).init.
> However, it's not always there (could be null if T.init is all zero).
I knew that about null once .. a year ago or so. Thanks for
the reminder.
> What we could do, however, is make one copy of an addressable T.init:
>
> template initialValue(T)
> {
> static immutable T initialValue = T.init;
> }
>
> that was used wherever it's needed, instead of creating a new one for
> every time you need it.
Yeah, why not. On second thought it is probably ok to let the
compiler chose the optimal assignment strategy: assign only
fields which are not void-initialized, memcpy from ROM or
zero-fill. Whether DMD is doing that at the moment is another
question, but I'm all for letting the compiler handle the
dirty details.
I guess what I was really looking for is a way to tell the
compiler that my `T* t` is uninitialized or "raw" and I want
it initialized like the compiler would do with a `T t` on the
stack: `t` is not destructed, nor is opAssign called on it.
Potentially "optimal" code is generated to satisfy the .init
state.
--
Marco
