Re: totally satisfied :D
On Monday, 17 September 2012 at 07:16:15 UTC, Jonathan M Davis wrote: On Monday, September 17, 2012 09:05:48 David Nadlinger wrote: On Sunday, 16 September 2012 at 21:59:30 UTC, Jøn wrote: > The best idea I had today: rename D into :D > > * Easier to google You might be surprised to see that D is the number 1 result for ":D" even today. The search results seem to be identical whether you search for D or :D, so the colon seems to be ignored. Of course, the fact that dlang.org comes up first could just be because google taylors its results to you, and we're both people who deal with D (and presumably search for it from time to time) already. - Jonathan M Davis It's the second result on DuckDuckGo, which *doesn't* tailor it's search results. https://duckduckgo.com/?q=d
SHA-3 is KECCAK
With the recent discussions regarding std.crypt/std.hash, I thought it would be worth announcing that the SHA-3 competition has ended and the winner is KECCAK. http://csrc.nist.gov/groups/ST/hash/sha-3/winner_sha-3.html
Re: Timsort vs some others
On Monday, 17 December 2012 at 15:28:36 UTC, bearophile wrote: Regarding the recent Phobos improvements that introduce a Timsort: http://forum.dlang.org/thread/50c8a4e67f79_3fdd19b7ae8146...@sh3.rs.github.com.mail I have found a blog post that compares the performance of Timsort, Smoothsort, and std::stable_sort: http://www.altdevblogaday.com/2012/06/15/smoothsort-vs-timsort/ Bye, bearophile While Smoothsort may be mathematically sound, it simply doesn't translate well to computer hardware. It's a variant of heap sort which requires a great deal of random access, whereas Timsort is a variant of merge sort which is largely sequential and benefits from the CPU cache. Furthermore, the Leonardo heap is much more computationally expensive than a typical binary or ternary heap. Both Timsort and Smoothsort are what you call "natural sorts," meaning they typically require fewer comparisons on data with low entropy. They're also rather complex which means added overhead. When sorting primitive types like int, comparisons are inexpensive, so the overhead makes these algorithms slower. But had he tested it on a data type like strings, then we'd likely see Timsort take the lead. On purely random data, quick sort and merge sort will win most of the time. But Timsort has an advantage over Smoothsort of being an adaptive algorithm; the so called "galloping mode," which is computationally expensive, is only activated when minGallop reaches a certain threshold and therefore beneficial. Otherwise, a simple linear merge is used (i.e. merge sort). On another note, I highly doubt that std::sort uses a "median of medians" algorithm, which would add much overhead and essentially double the number of comparisons required with little to no benefit. More likely, it simply chooses the pivot from a median of three.
Re: Timsort vs some others
On Tuesday, 18 December 2012 at 15:27:07 UTC, Joseph Rushton Wakeling wrote: On 12/18/2012 07:52 AM, Xinok wrote: While Smoothsort may be mathematically sound, it simply doesn't translate well to computer hardware. It's a variant of heap sort which requires a great deal of random access, whereas Timsort is a variant of merge sort which is largely sequential and benefits from the CPU cache. Furthermore, the Leonardo heap is much more computationally expensive than a typical binary or ternary heap. ... but I would guess that given the O(1) memory requirements it probably scales much better to sorting really, really large data, no? Heap sort actually performs really well if the entirety of the data is small enough to fit into the CPU cache. But on larger data sets, heap sort is jumping all over the place resulting in a significant number of cache misses. When a block of memory is stored in cache, it doesn't remain there for long and very little work is done on it when it is cached. (I mention heap sort because the leonardo heap of smoothsort is still very computationally expensive) Although merge sort is O(n), it's sequential nature results in far fewer cache misses. There are three blocks of memory being operated on at anytime: the two blocks to be merged, and a temporary buffer to store the merged elements. Three (or four) small pieces of memory can be sorted in the cache without any cache misses. Furthermore, thanks to the divide-and-conquer nature of merge sort, fairly large sublists can be sorted entirely in the CPU cache; this is even more so if you parallelize on a multi-core CPU which has a dedicated L1 cache for each CPU. Merge sort can be further optimized by using insertion sort on small sublists... which happens entirely in the CPU cache... Another way to put it, merge sort is an ideal algorithm for sorting linked lists, and it was even practical for sorting large lists stored on tape drives. Quick sort is a sequential sorting algorithm with O(log n) space complexity which is likely the reason it outperforms merge sort in most cases, albeit not being stable.
Re: Timsort vs some others
On Tuesday, 18 December 2012 at 15:55:17 UTC, Andrei Alexandrescu wrote: Another approach I wanted to try was to choose the median of K with K increasing with the size of the array. This is because a good pivot is more important for large arrays than for small arrays. As such, a possibility would be to simply sort a stride of the input (std.range.stride is random access and can be sorted right away without any particular implementation effort) and then choose the middle of the stride as the pivot. If anyone has the time and inclination, have at it! Perhaps a "median of log n" is in order, but the trouble is finding an algorithm for picking the median from n elements. The so called "median of medians" algorithm can choose a pivot within 30-70% of the range of the median. Otherwise, there doesn't seem to be any algorithm for choosing the absolute median other than, say, an insertion sort. I came up with this clever little guy a while ago which I used in my implementation of quick sort: http://dpaste.dzfl.pl/b85e7ad8 I would love to enhance it to work on a variable number of elements, but from what I can comprehend, the result is essentially a partial heap sort.
Re: Timsort vs some others
On Wednesday, 19 December 2012 at 02:00:05 UTC, Andrei Alexandrescu wrote: You don't need to choose a median - just sort the data (thereby making progress toward the end goal) and choose the middle element. I don't think it would work well in practice, but I'll put something together to see if the idea does have merit.
Re: Timsort vs some others
On Wednesday, 19 December 2012 at 05:48:04 UTC, Andrei
Alexandrescu wrote:
On 12/18/12 11:37 PM, Xinok wrote:
On Wednesday, 19 December 2012 at 02:00:05 UTC, Andrei
Alexandrescu wrote:
You don't need to choose a median - just sort the data
(thereby making
progress toward the end goal) and choose the middle element.
I don't think it would work well in practice, but I'll put
something
together to see if the idea does have merit.
I mostly fear cache touching issues.
Andrei
I based my little experiment on my 'unstablesort' module, located
here:
https://github.com/Xinok/XSort/blob/master/unstablesort.d
The results (sorting a random array of 1024*1024 uints):
Median of Five:
142ms 21627203 comps
Median of log n:
152ms 20778577 comps
The code:
size_t choosePivot(R range)
{
import std.math;
// Reserve slice of range for choosing pivot
R sub = range[0 .. cast(uint)log2(range.length) | 1];
// Pull in equally distributed elements
swap(sub[sub.length - 1], range[range.length - 1]);
foreach(i; 1 .. sub.length - 1) swap(sub[i], range[range.length
/ sub.length * i]);
// Sort sublist to choose pivot
insertionSort(sub);
// Move partitionable elements
sub = sub[piv + 1 .. sub.length];
foreach(i; 0 .. sub.length) swap(sub[i], range[range.length -
sub.length + i]);
// Return index of pivot
return sub.length / 2;
}
My thoughts, while the idea does have merit, I think the median
of five does a good job as it is. If you're interested in
reducing the number of comparisons, replacing
"optimisticInsertionSort" in std.algorithm with a binary
insertion sort will do much more to achieve that goal. And if
you're interested in O(n log n) running time, then add heap sort
as a fall-back algorithm, as I did in my module (I actually plan
to do this myself ... eventually).
Re: Should Phobos use Timsort instead? (with a small tweak)
On Saturday, 29 December 2012 at 19:07:52 UTC, Dmitry Olshansky wrote: Let me point out that Phobos has got the Timsort for stable sort in 2.061. It's precisely the work of Xinok that was integrated after going through many rounds of review. It would great to analyze the extra trick that reduces the amount of memory required. If it's proven to be a good speed-size trade-off then it could be integrated. I suppose it's worth a try. The trick in question takes two large runs and reduces them into several smaller runs for merging. The problem I foresee is that this may negatively affect the galloping mode of Timsort, which is most effective when merging two large runs. But I'll add this as a feature to my Timsort module anyways and see what effect it has.
Should Phobos use Timsort instead? (with a small tweak)
Recently, I've been working on my sorting algorithm, doing what I can before I implemented it into std.algorithm. Recently, I've found myself referring to Timsort for ways to optimize my algorithm, but that made me think, why not use Timsort instead? It was originally designed for Python, but it was apparently good enough for Java to adopt it as well. I think Phobos would benefit most from a good implementation of Timsort, perhaps enough to even ditch the unstable sort which I've found has some bad test cases (try sorting swapRanges(arr[0..$/2], arr[$/2..$])). My algorithm is very similar to Timsort, but Timsort is more highly tuned, so it would probably beat my algorithm in most cases. In a few benchmarks I've seen, Timsort even beats quicksort. The only downside is that Timsort may require up to O(n/2) additional space, and if it fails to allocate enough memory, it simply fails to sort the list. That's the benefit of my algorithm, it allocates O(n/1024) additional space by default and can reduce it further if needed. However, the "range swap" that my algorithm uses could easily be added to Timsort as well, so we could have the best of both worlds: The speed of Timsort with the low memory requirement of my algorithm. This is my proposal: Replace the stable (and unstable?) sort in Phobos with Timsort, including the additional range swap step. An explanation of Timsort can be found here: http://svn.python.org/projects/python/trunk/Objects/listsort.txt My algorithm can be found here (see the blog for more details): https://sourceforge.net/projects/xinoksort/
Re: Should Phobos use Timsort instead? (with a small tweak)
On 11/7/2011 7:47 PM, dsimcha wrote: Phobos definitely needs a decent stable sort. I had been meaning to contribute a very highly tuned merge sort that I use for some statistical calculations after allocators get into Phobos. Timsort would make a good additional option. However, I **strongly** recommend against **replacing** a sort that does not require O(n) extra space with one that does. Take a look at the graphic here: http://cl.ly/3L1o111u1M232q061o2N That's the extra step that I propose adding to Timsort, if it were implemented in Phobos. By doing a single range swap, you can reduce the space requirement from O(n/2) to O(n/4). My algorithm utilizes it so that only O(n/1024) additional space is required. Timsort would still use up to O(n/2) space, but if it failed to allocate enough memory, it could resort to the range swap instead. I'll leave it up to the community to decide what's best. But if the stable sort proves to be faster, has a worst case of O(n log n), and can succeed despite failing to allocate additional space, what purpose is there in keeping the unstable sort?
Re: Should Phobos use Timsort instead? (with a small tweak)
On 11/7/2011 10:44 PM, Andrei Alexandrescu wrote: On 11/7/11 9:28 PM, Xinok wrote: On 11/7/2011 7:47 PM, dsimcha wrote: Phobos definitely needs a decent stable sort. I had been meaning to contribute a very highly tuned merge sort that I use for some statistical calculations after allocators get into Phobos. Timsort would make a good additional option. However, I **strongly** recommend against **replacing** a sort that does not require O(n) extra space with one that does. Take a look at the graphic here: http://cl.ly/3L1o111u1M232q061o2N That's the extra step that I propose adding to Timsort, if it were implemented in Phobos. By doing a single range swap, you can reduce the space requirement from O(n/2) to O(n/4). My algorithm utilizes it so that only O(n/1024) additional space is required. Timsort would still use up to O(n/2) space, but if it failed to allocate enough memory, it could resort to the range swap instead. I'll leave it up to the community to decide what's best. But if the stable sort proves to be faster, has a worst case of O(n log n), and can succeed despite failing to allocate additional space, what purpose is there in keeping the unstable sort? Would be great to provide a better implementation of both stable and unstable sort. The part about requiring extra memory may be problematic, but we may use e.g. an additional policy parameter to decide on that. One thing I find confusing about the "range swap" operation that you rely on and mention in http://cl.ly/3L1o111u1M232q061o2N (and in the description of xinok sort which I skimmed without being able to understand) is that the example does not reflect the generality alluded to in the text. For example, the circled ranges at the top satisfy three conditions: 1. They are adjacent 2. Each is sorted 3. Each element in the left range is greater than any element in the right range 4. They have the same size (four elements each) It is unclear how many of these conditions must be _actually_ satisfied for range swap to work. Are all needed? The use of "half" and "merged" is also quite casual. I wish a clearer description were available. At any rate, if a provably better algorithm than what's in Phobos is available, we should include it in Phobos. I'm glad people find the necessity of a faster stable sort algorithm - it reflects maturity and sophistication in the community. Andrei 1. Yes. As mentioned in the graphic, the key is to move the smallest values to the left half, and the largest values to the right half. Since in a sorted list, the smallest values are at the beginning, and the largest values are at the end, the two ranges to swap will always be adjacent. 2. Yes. As you know, merge sort works by recursively merging two sorted lists into one sorted list. Merge sort generally requires O(n) space, or O(n/2) space if you only make a copy of the smaller half. The graphic intends to show how range swap reduces the space requirement. Instead of doing one large merge, you do two smaller merges. 3. Yes, see #1. 4. Yes. The "range swap" literally swaps two ranges of elements, so they must be equal in length. If you're still confused, think of it like this: In quick sort, you choose a pivot value, then you move all smaller values to the left of the pivot, and all larger values to the right of the pivot. Once you do this, there's no need to move any value in the left half to the right half, and vice versa. Similarly, range swap moves all the smallest values to the left half, and all the largest values to the right half, so there's no need to move values between the two halves.
Re: Add pragma(error) and pragma(warning) to the language.
On 11/10/2011 2:08 PM, Tobias Pankrath wrote: I'm currently writing some template based code and there are situations, when I want to issue warnings or errors to users of my code. I know of pragma(msg), but the output will be formatted differently from the normal compiler warnings / errors. This is bad for tool integration and the messages will likely not catch the eye of a normal user. Therefore I propose to add two pragmas pragma(error) and pragma(warning) to the core language, which work just like pragma(msg), but will format the message the way, the compiler would format its own error messages or warnings. pragma(error) should cause a real compile error, too. What do you think? I'm not against this idea, but I'd prefer that actual compiler warnings & errors would be distinguishable from those thrown by code.
Re: Why not extend array operations to full Fortran90 power ?
On 11/16/2011 2:08 PM, Joachim Wuttke wrote: Compare (1) Y[] = X[]*X[]; (2) Y[] = sin( X[] ); With gdc 4.4.6, (1) compiles and executes as I expected, whereas (2) is not allowed (fails at compile time). Why? The semantics of (2) is unambiguous, and it works perfectly well in Fortran90. Allowing (2) would make D really attractive for formula-heavy mathematical work. - Joachim I think vector operations are designed to avoid turning them into loops. In (2), this would require several calls to sin().
Re: Why not extend array operations to full Fortran90 power ?
On 11/16/2011 4:48 PM, Simen Kjærås wrote:
On Wed, 16 Nov 2011 22:31:31 +0100, Xinok wrote:
On 11/16/2011 2:08 PM, Joachim Wuttke wrote:
Compare
(1) Y[] = X[]*X[];
(2) Y[] = sin( X[] );
With gdc 4.4.6,
(1) compiles and executes as I expected, whereas
(2) is not allowed (fails at compile time).
Why?
The semantics of (2) is unambiguous,
and it works perfectly well in Fortran90.
Allowing (2) would make D really attractive
for formula-heavy mathematical work.
- Joachim
I think vector operations are designed to avoid turning them into
loops. In (2), this would require several calls to sin().
Really? How would you do Y[] = X[] * X[] without a loop?
That's not what I meant by it. Perhaps an example is in order:
void main(){
int rand(){
rndGen.popFront();
return rndGen.front;
}
int[5] a;
int[5] b = [1000, 2000, 3000, 4000, 5000];
a[] = b[] + (rand() % 1000);
writeln(a);
}
This is the result:
[1299, 2299, 3299, 4299, 5299]
It adds the same random value to each element, meaning it only calls
rand() once. D doesn't treat vector operations like loops.
Re: Why not extend array operations to full Fortran90 power ?
On 11/16/2011 2:08 PM, Joachim Wuttke wrote: (1) Y[] = X[]*X[]; (2) Y[] = sin( X[] ); I realized a problem with (2), it's actually not possible to rewrite it using existing constructs because foreach doesn't support multiple iterators. You can use std.range.zip: foreach(i; zip(Y, X)) i[0] = sin(i[1]); But it's not a core language feature. Before we could extend array operations to support the example above, I think D would need native support for multiple iterators.
Re: Website message overhaul
On 11/13/2011 8:50 PM, Andrei Alexandrescu wrote: Walter and I have been working on the website for a while. We want to crystallize a clear message of what the D programming language is. Please take a look at http://d-programming-language.org/new/. The work is content-only (no significant changes in style, though collapsible examples and twitter news are a new style element). Feedback is welcome. Thanks, Andrei I would suggest adding a single paragraph at the beginning which summarizes the language and it's benefits. It should be straight to the point. The first item on that page is type deduction, which isn't a good way to start. What type of language is it? It's a statically typed language which compiles to native machine code, but with modern features like garbage collection or dynamic arrays. What are its benefits? Higher productivity, fewer bugs, native speed, fast compilation. Those are the first things to come to mind when I think of D. Then in the following bullet points, you can provide examples and break it down in greater detail.
Re: Website message overhaul
On 11/17/2011 9:21 PM, Andrei Alexandrescu wrote: On 11/17/11 11:48 AM, Xinok wrote: What are its benefits? Higher productivity, fewer bugs, native speed, fast compilation. As opposed to other languages that have lower productivity, more bugs, less speed and slower compilation as goals. When a person visits the site for the first time, there's two things they want to know immediately: What and why? Besides for providing the "what", a description of the language, it's also important to answer, Why D? What is D's purpose? What does it excel at? Why would I want to use it? You don't have to use my example, but I think it's a good idea to include something along those lines.
Re: Website message overhaul
On 11/18/2011 11:01 AM, Andrei Alexandrescu wrote: On 11/18/11 7:22 AM, Nick Sabalausky wrote: "Andrei Alexandrescu" wrote in message news:ja4fhd$2amk$1...@digitalmars.com... On 11/17/11 11:48 AM, Xinok wrote: What are its benefits? Higher productivity, fewer bugs, native speed, fast compilation. As opposed to other languages that have lower productivity, more bugs, less speed and slower compilation as goals. As opposed to other langauges that either don't have all those as major goals, or do a poor job of them. These are too "motherhood and apple pie" kind of things, and too vague to be useful. Andrei That's why you go into more detail in the following bullet points. There are lots of terms you could use to describe a programming language: Strict, flexible, powerful, expressive, explicit, etc. Not all of these terms apply to D, so while they may be vague, they still give the newcomer a general idea. What is too vague is the terms at the top of the page, it sounds like a commercial for a hygiene product. "Intriguing, elegant, Loreal." D is a systems programming language which seamlessly integrates imperative, functional, object-oriented, low-level, and meta-programming styles into a single package. D compiles directly to machine code, so you get the efficiency of native executables with the convenience and productivity of modern languages. * I used the word 'efficiency' to describe native executables. D programs aren't necessarily faster, but they don't require an external runtime like Java or .NET. I find D programs have faster startup times and lower memory usage because of that. * Rather than saying "multi-paradigm", I went into a little more detail, listing the programming styles supported by D. "Low-level" refers to features like pointers, and inline assembly which is standard. * Providing links to external sources (Wikipedia) on certain terms may help to avoid confusion about what those terms actually mean in the context of D. * I'm just trying to get the ball rolling on this. I'm sure somebody else will write a better paragraph which puts mine to shame.
Re: Announcement list for breaking language changes?
On 11/27/2011 7:01 AM, Dejan Lekic wrote: D ChangeLog gives all such information, I believe. They are, but they're mixed with other changes and bug fixes. You have to read each item in the changelog to find the breaking changes. Listing them separately would help greatly when updating code.
Try Expression
Instead of having to write if(is(typeof(exp))), how about if(try(exp)) ?
Could D benefit from JIT compiling?
Reading through the 'Java > Scala' thread, I've realized there are some benefits to dynamic code generation vs statically compiled code. Things like unrolling loops, devirtualizing functions, etc. So it made me wonder, could D benefit from such technology, not from a feature standpoint, but strictly optimization? I'm not familiar with the topic, but I imagine there could be a few situations that would benefit in terms of performance, as long as it doesn't affect interoperability.
Re: Poll of the week: How should std.regex handle unknown escape sequences as in: "[\.]"
On 12/2/2011 5:33 PM, Marco Leise wrote: http://www.easypolls.net/poll.html?p=4ed9478e4fb7b0e4886eeea2 I prefer that regexp engines are as consistent as possible. Everything I tested accepts this as a valid regular expression, so I think std.regex should as well.
Re: New Website Issues I've Found
On 12/10/2011 3:11 PM, Chad J wrote: I'm looking at http://www.d-programming-language.org and seeing the following problems: I found a few more issues as well: - The links to D 2.0 Changelog, D 1.0 Changelog, and D Programming Language Specification 2.0 are broken at http://www.d-programming-language.org/download.html - Scroll down a bit to "Download latest D 2.0 alpha", it links to DMD 2.040 at http://www.d-programming-language.org/changelog.html - I was looking for the page that documents the compiler switches but can't find it.
Re: versions and 32 vs 64-bit code
On 12/26/2011 8:23 AM, Andrej Mitrovic wrote:
On 12/26/11, Alex Rønne Petersen wrote:
Use:
version (D_LP64)
{
// 64-bit ...
}
else
{
// 32-bit ...
}
So why doesn't D_LP32 exist? If you already use "version(X86) else
version(X86_64)" you're going to have to swap all of your code around
if you start using D_LP64..
I agree, but I don't think D_LP32 would be correct since LP stands for
"long pointer".
Dlang.org needs a "Getting Started" page
Just a thought, but I think the official website really needs a Getting Started page for newcomers. This page should make it as effortless as possible by providing all the information and resources needed for one to dive right into D. Not everything needs to be covered by this page, but it should provide links as necessary. Just to list some things that should be covered on this page (you can list more): - Explanation of D 1.x, D 2.x, Phobos, and Tango. - Explanation and links to different compilers (DMD, GDC, etc) - Downloads - List of IDEs / Editors that support D - Tutorial: Writing and compiling a program in D - Books / Websites / Resources for learning D - Libraries for D (e.g. dsource.org) - Forums / Newsgroups / Newsgroup clients + instructions for configuring Most importantly, maintain this page! Never let it get out of date!
Re: Dlang.org needs a "Getting Started" page
On 1/31/2012 10:45 AM, Jesse Phillips wrote: Well, this is how Wiki4D[1] is set up. Actually that is basically all it is. I think you list is way to long for a single page. Improvements are welcome, it is maintained by anyone willing to look at it, including DigitalMars. 1. http://www.prowiki.org/wiki4d/wiki.cgi?FrontPage The problem is that newcomers shouldn't have to hunt for this information. While that link could suffice, it's simply unprofessional to force them to jump between websites to find the information they need. There needs to be an obvious place, a single well-structured page on the official website with everything they need to know to get started.
Re: Dlang.org needs a "Getting Started" page
On 1/31/2012 11:47 AM, Jesse Phillips wrote:
As I mentioned I think this list is too much for one page, it is just
overwhelming.
It doesn't have to be a wall of text. If done right, it would be a
well-structured page split up into sections which is easy to navigate
and find the information one would want.
Something I didn't make clear, I think it's okay to provide links to
other pages (in moderation, let's not just have a page full of links),
as long as those pages aren't out of date.
- Explanation of D 1.x, D 2.x, Phobos, and Tango.
This would be nice, but it too easy to be bias in describing the
situation, especially since it exists only for D 1.x which is being
phased out.
I don't see how it would be biased. Phobos is the official standard
library, Tango is a third-party standard library which is for D 1.x
only. D 2.x is the latest version while D 1.x is being phased out and
will be maintained until the end of 2012.
- Explanation and links to different compilers (DMD, GDC, etc)
There are links found when you select Tools & Downloads.
It doesn't provide any explanation though. The information is scattered
everywhere, you have to go hunting for it which only adds to the confusion.
- List of IDEs / Editors that support D
This list is overwhelming, subjective, and a link is provided to Wiki4D
from Tools & Downloads.
As I mentioned above, I think it's okay to provide a link rather than
having a large list. Perhaps it would be best to list a few popular
editors (DDT, VisualD) and provide that link for the rest.
- Tutorial: Writing and compiling a program in D
There is a link to the Tutorial chapter of "The D Programming Language"
under Documentation.
Once again, information is scattered and you have to go looking for it.
There's also other learning materials for D which aren't linked to
anywhere AFAIK.
- Books / Websites / Resources for learning D
Under Community there is a Links link, that is not well maintained.
>
- Libraries for D (e.g. dsource.org)
Under Links.
The list is very out of date, and "links" at the bottom of the page is
not an obvious place to look for this information.
- Forums / Newsgroups / Newsgroup clients + instructions for configuring
Community contains a link for Forms, or actually the Newsgroups and
provides the web interface for those not setting up a client. Yes this
needs updated and DFeed needs to move to d-programming-language.org.
Most importantly, maintain this page! Never let it get out of date!
No, update the pages that exist, and keep them up to date.
Ideally, the website would be maintained and easier to navigate.
However, it doesn't seem to be a high priority or else it would be done
already. At least this way, it's a single page which could be put up in
less than a day and is little effort to maintain. It's an obvious place
to look as well ("Getting Started", who wouldn't look there first?).
This page would serve as a single entry point which would help newcomers:
- Download and install the compiler
- Download / Configure an IDE or Editor
- Write and Compile their first program
- Find learning materials
- Find resources such as libraries and debuggers
- Get them involved in the community
- Participate in the development of D
That sounds worth it to me.
Re: D-
On 2/10/2012 8:13 PM, Tim Krimm wrote: If you make a subset of D, it would most likely be named Mini-D. But at that point you've got an enhanced C without going C++. Yes and that probably would be better than what I have now. Going back and forth programming in C/C++ today, and then switching back to D tomorrow. Let me see if I remember again, classes and structures are almost the same in C++ but different in D. Well I did the assignment A=B, if I change A will it also change B, or is B a copy of A. Is A a class or a structure that is an important distinction in D. Today, Oh crap I forgot the #include Tomorrow, Oh crap I forgot the import Oh crap what was that syntax for initializing the class variables again. That hardly seems like a good enough reason to create a second language. The community has enough to work on from the standard library to squashing bugs to writing literature and much more. I think a more practical idea would be to write a utility which translates a subset of D's features to equivalent C code.
Type deduction using switch case
While reading "The Right Approach to Exceptions", it gave me this
idea. The user would declare a list of variables of different
types as case statements, and the variable with matches the type
of the switch expression is used.
I don't know how the syntax should look, this is merely an
example:
void foo(T)(T arg){
switch(arg){
case int i:
writeln("Type is int ", i); break;
case float f:
writeln("Type is float ", f); break;
case string s:
writeln("Type is string ", s); break;
default:
writeln("Type is unknown"); break;
}
}
While static if would be more practical for templates, my idea
could be extended to dynamic upcasting of classes as well, which
could be applied to exception handling:
try{ ... }
catch(Throwable err) switch(err){
case IOError a:
break;
case OutOfMemoryError b:
break;
default:
throw err;
}
Re: Type deduction using switch case
On Sunday, 19 February 2012 at 00:49:56 UTC, Robert Jacques wrote:
On Sat, 18 Feb 2012 18:33:01 -0600, Xinok
wrote:
While reading "The Right Approach to Exceptions", it gave me
this
idea. The user would declare a list of variables of different
types as case statements, and the variable with matches the
type
of the switch expression is used.
I don't know how the syntax should look, this is merely an
example:
void foo(T)(T arg){
switch(arg){
case int i:
writeln("Type is int ", i); break;
case float f:
writeln("Type is float ", f); break;
case string s:
writeln("Type is string ", s); break;
default:
writeln("Type is unknown"); break;
}
}
The above should be switch (T) not switch(arg) for the example
to be correct.
Notice how it's "int i" and not just "int". Also notice how each
writeln statement also prints the variable. Each case statement
declares a variable, so it matches the type of the expression
against the type of the variable, and stores the switch
expression in that variable.
Re: Type deduction using switch case
On Sunday, 19 February 2012 at 06:28:37 UTC, Robert Jacques wrote:
On Sat, 18 Feb 2012 20:03:51 -0600, Xinok
wrote:
Notice how it's "int i" and not just "int". Also notice how
each
writeln statement also prints the variable. Each case statement
declares a variable, so it matches the type of the expression
against the type of the variable, and stores the switch
expression in that variable.
And why not simply do:
void foo(T)(T arg){
switch(T){
case int:
writeln("Type is int ", arg); break;
case float:
writeln("Type is float ", arg); break;
case string:
writeln("Type is string ", arg); break;
default:
writeln("Type is unknown"); break;
}
}
Because all of the code gets compiled in, so if one statement
uses the type incorrectly, it won't compile. It also doesn't
allow for dynamic upcasting of classes as in my second example.
Re: My Issues with Slices and AAs
On Saturday, 3 March 2012 at 05:00:53 UTC, Kevin wrote: Is there something on ranges that is more of a write-up. Something to explain purpose, implementation, usage, ...? Or if not some code that makes good use of ranges? Thanks, Kevin http://ddili.org/ders/d.en/ranges.html
Re: Random access range
On Thursday, 8 March 2012 at 16:43:25 UTC, zeljkog wrote:
import std.stdio;
struct Rar{
int[] data = [1,3,5];
int length = 3;
ref int opIndex(int i){ return data[i];}
}
void main() {
Rar x;
foreach (e; x)
writeln(e);
}
Error: invalid foreach aggregate x
Is'nt Rar valid random access range?
struct N(T){
T[] arr;
this(T[] other){ arr = other; }
this(N other){ arr = other.arr; }
// The declarations below are required
// The @property tag is also required
ref T opIndex(size_t i){ return arr[i]; }
@property size_t length(){ return arr.length; }
@property ref T front(){ return arr.front; }
@property ref T back(){ return arr.back; }
void popFront(){ arr.popFront(); }
void popBack(){ arr.popBack(); }
@property bool empty(){ return arr.empty; }
@property N save(){ return N(arr); }
}
Sort for forward ranges
This is a simple library I wrote for sorting forward ranges. It's an in-place unstable sort which uses a combination of quick sort and comb sort. It's about 2-3x slower than the Phobos unstable sort. The down side of using quick sort is choosing a pivot. Rather than walk the range to do a median-of-three or other trick, I simply use the first element as the pivot. Instead, the code will fall back to comb sort to avoid the worst-case of quick sort. http://www.mediafire.com/?yy8p5xzg8ka38rd
Regarding implementing a stable sort for Phobos
I've been playing with sorting algorithms a lot in recent months, so I want to implement a *working* stable sort for Phobos which is broken at the moment. I have a working library and I'm still adding to it. It's much more complex than a simple merge sort, being over 300 lines of code at the moment. - It's a natural merge sort, which is faster on partially sorted lists, and adds little overhead for mostly random lists. - It uses O(log n log n) additional space for merging. - I wrote it to sort random-access ranges *without* slicing, but I think the exclusion of slicing makes it slower. I'm writing a separate implementation which uses slicing and I'll keep it if it's much faster. - To avoid multiple allocations, the user can allocate their own temporary memory and pass it to the sort function. - I decided against using pointers. While I could use them to write highly optimized code for arrays, pointers can't be used in safe code and don't work very well in CTFE at the moment. Is it worth keeping the implementation *without* slicing? Many functions in Phobos do require slicing, including the unstable sort, and I think most random-access ranges do or could support slicing. What would you prefer in terms of memory usage vs performance? O(n/2) space is optimal for performance, O(1) (in-place) requires zero allocations but is slower, and O(log n log n) provides a good balance. Should I implement concurrency? Merge sort is very easy to parallelize, and being in-place or natural doesn't change this fact. Should we take a different path and go for a basic merge sort or even Timsort? I've considered writing a Timsort though that seems like daunting task to me, so here's an implementation written in C - https://github.com/swenson/sort
Re: Regarding implementing a stable sort for Phobos
On Tuesday, 13 March 2012 at 06:53:30 UTC, Chad J wrote: Hey, I'd love to see more sorting algorithms in phobos. Being stuck with one seems kind of... wrong. Things like this are better left to 3rd party libs. Phobos already has two, a stable and unstable sort, which fulfill 99% of cases. If the range is a linked list, shouldn't it be possible to do a merge sort with optimally in-place and use no extra memory whatsoever? I know it can be done in-place, but I've never benchmarked it. I wonder if it's worth considering, and how it would compare against array-based merge sort with allocations and such. Yes, it's possible because insertions are inexpensive in linked lists. However, it would be impractical to implement one at the moment because Phobos has no concept of linked lists (ranges wouldn't cover it). Although it's probably out of your scope right now, I'd like to see insertion sort some day. I would use it for things like broadphase sorting in collision detection (that is, you sort everything by say, x coordinates first, and then you can walk through the whole simulation from left-to-right and have very few things to check collisions for at each point). Since the ordering of the objects in the simulation is unlikely to change much between frames, it will be almost entirely sorted each time. I have to imagine insertion sort would be awesome at that; nearly O(n). Maybe if it hits more than log(n) nonlocal insertions it would bail out into a merge sort or something. Insertion sort is one of the simplest sorts to write. I use it to optimize this stable sort as its super efficient at sorting small sublists. A natural merge sort would also work well in this case, but Timsort would work best. Timsort is also a natural merge sort, but it goes much farther than that.
Re: Regarding implementing a stable sort for Phobos
On Tuesday, 13 March 2012 at 08:37:06 UTC, deadalnix wrote: I have a radix sort (that need some rework to be phobos quality) and a smoothsort (that could be included in phobos). Would you mind sharing your smoothsort? I haven't implemented one myself and I'd love to test it out. Radix sort, on the other hand, is not a comparison sort. You'd have to rewrite it for every possible element and container type. I have a sort for ForwardRange, but it is O(n²) and unstable. However, it is in place. I posted one a few days ago myself - http://forum.dlang.org/thread/cmipnxrarexjgnrdq...@forum.dlang.org I don't think we should allocate behind one's back, so merge sort should be an option, unless called explicitely. When it comes to stable sorts, merge sort is the best choice. I found tree sort to be quite slow (using RedBlackTree in std.container), and a stable quick sort is still slower than a merge sort. So I guess that'd mean an in-place merge sort. I've implemented one which was 3x slower than quick sort. Allocating even a small amount of space makes a big difference. smoothsort is a good solution for that. radix is also guarantee to be O(n). Insertionsort is quite risky, because it can ends up in O(n²) very easily.
Re: Regarding implementing a stable sort for Phobos
On Tuesday, 13 March 2012 at 09:32:49 UTC, deadalnix wrote: Le 13/03/2012 10:19, Xinok a écrit : Would you mind sharing your smoothsort? I haven't implemented one myself and I'd love to test it out. It is on github : https://github.com/deadalnix/Dsort/blob/master/sort/smooth.d Thanks. I found a couple cases where it performs better, but overall, the overhead of the algorithm seems to be too much and most other algorithms performed better. While some need to be rewritten, I have a slew of algorithms if you want them for your project.
Re: Regarding implementing a stable sort for Phobos
On Tuesday, 13 March 2012 at 14:31:59 UTC, Andrei Alexandrescu wrote: On 3/13/12 1:31 AM, Xinok wrote: - It's a natural merge sort, which is faster on partially sorted lists, and adds little overhead for mostly random lists. - It uses O(log n log n) additional space for merging. That's 1024 when n is 4 billion. I think you can safely approximate it with alloca or a fixed-size stack-allocated array. How about stack allocated for small lists, and heap allocated for larger lists? e.g. Limit the stack to 1KiB and use the heap for anything larger. - I wrote it to sort random-access ranges *without* slicing, but I think the exclusion of slicing makes it slower. I'm writing a separate implementation which uses slicing and I'll keep it if it's much faster. Having random access implies having slicing. - To avoid multiple allocations, the user can allocate their own temporary memory and pass it to the sort function. If you need different allocation strategies, I suggest you make it a policy (like stability is). - I decided against using pointers. While I could use them to write highly optimized code for arrays, pointers can't be used in safe code and don't work very well in CTFE at the moment. Perhaps it's best to have two distinct implementations guarded by if (__ctfe). The runtime implementation can be @trusted. If the performance gain is great enough, I'll consider doing that. Is it worth keeping the implementation *without* slicing? Many functions in Phobos do require slicing, including the unstable sort, and I think most random-access ranges do or could support slicing. No need. I'll leave it out of Phobos. What would you prefer in terms of memory usage vs performance? O(n/2) space is optimal for performance, O(1) (in-place) requires zero allocations but is slower, and O(log n log n) provides a good balance. The latter rounded up to a constant sounds best. Should I implement concurrency? Merge sort is very easy to parallelize, and being in-place or natural doesn't change this fact. Let's save that for std.parallel_algorithm. I'll leave it out of Phobos for now.
Re: Regarding implementing a stable sort for Phobos
On Tuesday, 13 March 2012 at 16:04:55 UTC, deadalnix wrote: Le 13/03/2012 16:08, Xinok a écrit : On Tuesday, 13 March 2012 at 09:32:49 UTC, deadalnix wrote: Le 13/03/2012 10:19, Xinok a écrit : Would you mind sharing your smoothsort? I haven't implemented one myself and I'd love to test it out. It is on github : https://github.com/deadalnix/Dsort/blob/master/sort/smooth.d Thanks. I found a couple cases where it performs better, but overall, the overhead of the algorithm seems to be too much and most other algorithms performed better. smooth sort is intended to be used on semi sorted data (like transparent polygons on a 3D scene). Ideal to keep some data sorted. It also have a guarantee to run in O(n*log(n)). But qsort variation (like we have in phobos) is faster in the general case. It only performs well if there aren't many elements to move around. For example, I took a sorted list with 1 million elements, and appended 64 random elements. Smoothsort was the second slowest, only marginally beating heap sort. My natural merge sort was 27x faster.
Re: Regarding implementing a stable sort for Phobos
On Tuesday, 13 March 2012 at 16:11:05 UTC, Andrei Alexandrescu wrote: On 3/13/12 10:54 AM, Sean Kelly wrote: How does the built-in sort do? I ask because the sort routine I wrote works the same way, which is optimized for ranges with a lot of common elements. It's not about common (equal) elements, it's about elements for which comparisons do a lot of work because they have common prefixes. Consider: auto arr = [ "aaa", "aab", "aac", "aad" ]; sort!((a, b) => a > b)(arr); There will be a lot of redundant prefix comparisons because the sorting method doesn't have information about the common prefixes. Trie-based sorting is a more efficient method for ranges of ranges, see e.g. http://en.wikipedia.org/wiki/Burstsort. Andrei Rather than a sort function, I think we'd benefit more from Trie in std.container. If implemented correctly, it could be self sorting like RedBlackTree.
Re: Regarding implementing a stable sort for Phobos
On Tuesday, 13 March 2012 at 06:32:01 UTC, Xinok wrote: I've been playing with sorting algorithms a lot in recent months, so I want to implement a *working* stable sort for Phobos which is broken at the moment. I have a working library and I'm still adding to it. It's much more complex than a simple merge sort, being over 300 lines of code at the moment. I've implemented slicing which has improved benchmarks quite a bit. Sorting a random array of 1 million uints: Phobos Unstable Sort - 132ms Phobos Stable Sort - 2037ms Proposed Stable Sort - 187ms Sorting a random array of 1 million strings: Phobos Unstable Sort - 1228ms Phobos Stable Sort - 3516ms Proposed Stable Sort - 1178ms It still uses O(log n log n) space. I modified the code to allocate up to 1KiB on the stack, and use the heap for anything larger. I simply marked the entry sort function as @trusted. The non-slicing code is still in the lib but disabled. I've yet to add contracts, documentation, and a unittest. I won't be adding optimized code for arrays utilizing pointers as I expect the performance gain to be as little as 10%. You can download the preliminary lib here: http://www.mediafire.com/?ux49x30dj483dqg
Re: Regarding implementing a stable sort for Phobos
On Tuesday, 13 March 2012 at 18:32:27 UTC, Xinok wrote: On Tuesday, 13 March 2012 at 06:32:01 UTC, Xinok wrote: I've been playing with sorting algorithms a lot in recent months, so I want to implement a *working* stable sort for Phobos which is broken at the moment. I have a working library and I'm still adding to it. It's much more complex than a simple merge sort, being over 300 lines of code at the moment. I've implemented slicing which has improved benchmarks quite a bit. It still uses O(log n log n) space. I modified the code to allocate up to 1KiB on the stack, and use the heap for anything larger. I simply marked the entry sort function as @trusted. The non-slicing code is still in the lib but disabled. I've yet to add contracts, documentation, and a unittest. I won't be adding optimized code for arrays utilizing pointers as I expect the performance gain to be as little as 10%. A second update: http://www.mediafire.com/?gqejl17ob1ywyat I removed the code without slicing from the lib, though I still retain a copy. I added 3 unittests: A basic sort test, a stability test, and a CTFE test. I added a few asserts which have helped me discover bugs in the past. I only added basic documentation. I've found it difficult to explain to others how an in-place merge sort works, so I didn't bother. I've ran the code through several tests. It works, it's stable, and it consistently gives good performance. So for the all important question: Does anybody want to implement it in std.algorithm for me? I've looked at the code in std.algorithm, and all I can tell is that sortImpl is a recursive function. I have no idea what it's doing or what I need to change.
Re: Regarding implementing a stable sort for Phobos
On Wednesday, 14 March 2012 at 03:55:31 UTC, Xinok wrote: I removed the code without slicing from the lib, though I still retain a copy. I added 3 unittests: A basic sort test, a stability test, and a CTFE test. I added a few asserts which have helped me discover bugs in the past. I only added basic documentation. I've found it difficult to explain to others how an in-place merge sort works, so I didn't bother. Third update: http://www.mediafire.com/?9jx07estd58wh2p + Added in-place sorting; Set template argument inPlace to true + Fixed CTFE compatibility issues + Vastly improved unittest + CTFE unittest will no longer stop compilation upon failure; It will print a warning instead + Optimization: Recurse into smaller half, use tail call on larger half - CTFE test fails under DMD; Other compilers untested I currently don't know why CTFE fails. The test performed at compile-time is the exact same test that passes at runtime. The code executes successfully but the array is not sorted correctly. By implementing a tail call, in-place sorting should only use O(log n) space on the stack, though at the cost of performance. Sorting a random array of 1 million uints: Phobos Unstable Sort - 132ms Phobos Stable Sort - 2037ms Proposed Stable Sort - 187ms In-Place Stable Sort - 355ms Sorting a random array of 1 million strings: Phobos Unstable Sort - 1228ms Phobos Stable Sort - 3516ms Proposed Stable Sort - 1178ms In-Place Stable Sort - 1422ms Number of Comparisons on 1 million elements: Phobos Unstable Sort - 24813812 Phobos Stable Sort - 25304078 Proposed Stable Sort - 19777088 In-Place Stable Sort - 21212726
Re: Interesting Memory Optimization
On Friday, 16 March 2012 at 02:18:27 UTC, Kevin wrote: This is in no way D specific but say you have two constant strings. const char[] a = "1234567890"; // and const char[] b = "67890"; You could lay out the memory inside of one another. IE: if a.ptr = 1 then b.ptr = 6. I'm not sure if this has been done and I don't think it would apply very often but it would be kinda cool. I thought of this because I wanted to pre-generate hex-representations of some numbers I realized I could use half the memory if I nested them. (At least I think it would be half). Kevin. I'm pretty sure this is called string pooling.
Re: Interesting Memory Optimization
On Friday, 16 March 2012 at 15:41:32 UTC, Timon Gehr wrote:
On 03/16/2012 03:28 PM, H. S. Teoh wrote:
More to the point, does dmd perform this optimization
currently?
T
No.
immutable string a = "123";
immutable string b = a;
void main(){writeln(a.ptr is b.ptr);} // "false"
It actually does, but only identical strings. It doesn't seem to
do strings within strings.
void foo(string a){
string b = "123";
writeln(a is b);
}
void main(){
string a = "123";
string b = "456";
string c = "123456";
foo(a);
foo(b);
foo(c);
}
Prints:
true
false
false
Re: Interesting Memory Optimization
On Friday, 16 March 2012 at 18:44:53 UTC, Xinok wrote:
On Friday, 16 March 2012 at 15:41:32 UTC, Timon Gehr wrote:
On 03/16/2012 03:28 PM, H. S. Teoh wrote:
More to the point, does dmd perform this optimization
currently?
T
No.
immutable string a = "123";
immutable string b = a;
void main(){writeln(a.ptr is b.ptr);} // "false"
It actually does, but only identical strings. It doesn't seem
to do strings within strings.
void foo(string a){
string b = "123";
writeln(a is b);
}
void main(){
string a = "123";
string b = "456";
string c = "123456";
foo(a);
foo(b);
foo(c);
}
Prints:
true
false
false
Captain obvious to the rescue, 'is' is false if the strings are
of different lengths >.<. But it still stands, D doesn't dedup
strings within strings.
void main(){
string a = "123";
string b = "123456";
writeln(a.ptr);
writeln(b.ptr);
writeln(a.ptr);
writeln(b.ptr);
}
Prints:
44F080
44F090
44F080
44F090
I printed it twice to ensure it wasn't duping the strings.
Re: Interesting Memory Optimization
On Friday, 16 March 2012 at 18:56:00 UTC, Timon Gehr wrote:
It can't because there must be a terminating zero byte. It does
not do it even if it could though.
immutable string x = "123";
immutable string y = "123";
void foo(string a){
string b = "123";
writeln(a is b);
}
void main(){
string a = "123";
string b = "456";
string c = "456123";
foo(c[3..$]);// false
writeln(x is y); // false
writeln(a is x); // false
writeln(b is x); // false
writeln(a is y); // false
writeln(b is y); // false
foo(a); // true
foo(b); // false
}
So while D does pool strings, it doesn't seem to optimize
globals. I couldn't find anything about it on the bug tracker.
Re: Understanding Templates: why can't anybody do it?
On Saturday, 17 March 2012 at 18:16:31 UTC, Walter Bright wrote: i.e. templates are type parameters. Maybe in C++. In C++, templates are attached to a class or function, where as in D, they're an independent construct. The way I think of it, templates are a tool for building static code from a set of parameters. String mixins are a similar tool which are more powerful but less elegant. Programmers will use templates for unintended purposes, but that doesn't change what they are. You can use full closures to store references to variables, but that doesn't make functions reference types.
Re: What about putting array.empty in object.d?
On Wednesday, 21 March 2012 at 04:54:54 UTC, Daniel Murphy wrote: FWIW, I would rather see `if (array)` translated to `if (array.length)` and this become the recomended way to check if an array is empty. Wouldn't that remove the dependency on std.array for most of the cases? Nope. .length is a requirement for finite random-access ranges, but not for forward or bidirectional ranges. .empty is the only primitive required by all input ranges. So if you pass an array to a function expecting a forward range, it may not work if the primitive .empty doesn't exist.
Re: Array ops give sharing violation under Windows 7 64 bit?
On Saturday, 24 March 2012 at 19:08:00 UTC, Walter Bright wrote: On 3/24/2012 11:55 AM, Walter Bright wrote: I'm mystified. Does anyone have any ideas? If I add a del test.exe to the cc.bat file: ..\dmd test test del test.exe ..\dmd test --- It now fails with GetLastError() of 5, meaning "Access is denied." The cc.bat file has to be executed repeatedly for this to happen. I wonder if it may have something to do with the operating system delayed writes? If you have an antivirus, try disabling it before compiling.
Re: Regarding implementing a stable sort for Phobos
On Thursday, 15 March 2012 at 20:20:59 UTC, Xinok wrote: Third update: http://www.mediafire.com/?9jx07estd58wh2p + Added in-place sorting; Set template argument inPlace to true + Fixed CTFE compatibility issues + Vastly improved unittest + CTFE unittest will no longer stop compilation upon failure; It will print a warning instead + Optimization: Recurse into smaller half, use tail call on larger half - CTFE test fails under DMD; Other compilers untested One more update. I created a repository on GitHub where I'll host the module from now on: https://github.com/Xinok/XSort + Added concurrency + Optimized swapBlocks; 10% improvement in benchmarks + Fixed and enhanced unittest + Extended documentation of stableSort function - Concurrency fails to compile in debug builds so is enabled in release builds only - CTFE test still fails I'm still getting acquainted with Git and Phobos, not quite sure what I'm doing. Hopefully I can pull it together soon so Phobos can have a working stable sort.
Re: Nested functions should be exempt from sequential visibility rules
On Tuesday, 3 April 2012 at 12:13:00 UTC, Timon Gehr wrote:
On 04/03/2012 02:00 PM, Nick Sabalausky wrote:
"Timon Gehr" wrote in message
news:jlej27$mvi$1...@digitalmars.com...
This is the right way to work around this issue. It works now
and does not
imply any kind of overhead at runtime:
void foo(){
void a()(){ ... }
void b() { ... }
}
1. How the heck does that work?
Symbol lookup is done upon the first instantiation of the local
template.
Currently, it prints 365. But remove the commented line, and it
prints 500 twice. But it's a minor issue at worst that's easy to
avoid, and this is a very simple workaround.
int two()
{
return 500;
}
void main()
{
int x = 365;
int one()()
{
return two();
}
// writeln(one());
int two()
{
return x;
}
writeln(one());
}
I found another solution involving templates, though not as
convenient:
template foo()
{
int one(){
return two();
}
int two(){
return x + y;
}
int y = 12;
}
void main()
{
int x = 365;
mixin foo;
writeln(one());
}
Re: Predefined 'release' version?
On Friday, 20 April 2012 at 17:43:49 UTC, Ali Çehreli wrote:
On 04/20/2012 10:24 AM, Bernard Helyer wrote:
On Friday, 20 April 2012 at 15:26:24 UTC, H. S. Teoh wrote:
I just discovered to my dismay that dmd does not define
version=release
when compiling in -release mode. What's the reason for this?
I have some code that uses ctRegex, which slows down
compilation
significantly due to heavy amounts of CTFE, but which speeds
up the
final executable. I'd like to version this code and use
regular regex()
for non-release builds, and switch to ctRegex for release
builds. Yes I
can just pass in a version on the commandline, but it'd be
nice if it
could be triggered automatically by -release.
T
debug {
// blah
} else {
// fast blah
}
debug blocks are activated when -debug switch is explicitly
specified, not when -release is not specified. :)
Ali
The code in "else" will be used in release builds.
Alias Expressions
I know this has probably been asked for a hundred times before,
but I don't understand why D doesn't support this. Template alias
parameters can accept nearly anything as an argument that
standard aliases don't. I think standard aliases should be
equally as powerful as their template counterpart.
If you can write this:
template Eval(alias arg){ alias arg Eval; }
alias Eval!(cond ? a : b) al;
Why not simply allow this?
alias (cond ? a : b) al;
Or perhaps this:
alias al = cond ? a : b;
Re: Array-wise expressions
On Sunday, 6 January 2013 at 15:39:03 UTC, Lobachevsky wrote: Is there any plan to extend array-wise expressions to include calls to arbitrary "scalar" functions, i.e. auto a = [1.2, 2.3, 3.4]; auto b = [7.1, 8.2, 9.3]; auto c = new double[3]; c[] = sin( 4 * a[] + b[] ); or c[] = foo(a[], b[], 42); Performing this action would require several calls to foo. By convention, array operations aren't loops; it only calculates the R-value once, then sets all elements to the same value. I wrote this as a quick example: http://dpaste.dzfl.pl/4ba03ef6 It does get a random value, but it only calls rand() once so all of the elements in the array are set to the same random value.
Re: Exceptional coding style
On Monday, 14 January 2013 at 19:24:25 UTC, Walter Bright wrote: Quite a nice read on the coding style used in Doom. http://kotaku.com/5975610/the-exceptional-beauty-of-doom-3s-source-code?post=56177550 I think more important than any aspect of a particular coding style is that style guidelines ensure that code is written in a consistent manner. The advantage is that, even if it's a "bad" style, you can learn to read and write code in that style which makes things predictable. You learn conventions which tell you how to use classes and functions without the need to refer to documentation. When convention isn't enough, you learn where to find the information you need (can it be inferred from the code? is it clearly stated in a comment or documentation?). If nothing else, you simply learn to read and interpret code written in a certain style. It's certainly to the benefit of developers to have a good coding style. But the only thing worse than a bad coding style is a mix of styles which makes code inconsistent and unpredictable. There needs to be a consensus among the developers on a style guideline.
Re: Should range foreach be iterating over an implicit copy?
On Wednesday, 16 May 2012 at 21:40:39 UTC, Andrei Alexandrescu wrote: On 5/16/12 4:37 PM, Nick Sabalausky wrote: One counter-argument that was raised is that TDPL has an example on page 381 that indicates foreach iterates over an implicit copy. I don't have a copy handy ATM, so I can't look at it myself, but I'd love to see Andrei weigh in on this: I'm curious if this example in TDPL made that copy deliberately, or if the full implications of that copy were just an oversight. It is deliberate and the intent is that millions of programmers used to foreach from other languages don't scream "where is my range???" Andrei I think this is the correct behavior as well. Otherwise, we'd have to take extra care when writing generic code to ensure it doesn't consume the range but doesn't attempt to call .save on non-range types.
Increment / Decrement Operator Behavior
The increment and decrement operators are highly dependent on operator precedence and associativity. If the actions are performed in a different order than the developer presumed, it could cause unexpected behavior. I had a simple idea to change the behavior of this operator. It works for the postfix operators but not prefix. Take the following code: size_t i = 5; writeln(i--, i--, i--); As of now, this writes "543". With my idea, instead it would write, "555". Under the hood, the compiler would rewrite the code as: size_t i = 5; writeln(i, i, i); --i; --i; --i; It decrements the variable after the current statement. While not the norm, this behavior is at least predictable. For non-static variables, such as array elements, the compiler could store a temporary reference to the variable so it can decrement it afterwards. I'm not actually proposing we actually make this change. I simply thought it was a nifty idea worth sharing.
Re: Increment / Decrement Operator Behavior
On Monday, 4 June 2012 at 20:08:57 UTC, simendsjo wrote: Oh, and what should writeln(i++, ++i, ++i, i++) do? It is messy whatever the logic implementation. For prefix operators, it would be logical to perform the action before the statement, such as the code would be rewritten as: ++i ++i writeln(i, i, i, i) i++ i++ However, I already stated that it wouldn't work for prefix operators. Take this statement: ++foo(++i) There's no way to increment the return value of foo without calling foo first. This "logic" would only work for the postfix operators. I came up with the idea after refactoring this code: https://github.com/Xinok/XSort/blob/master/timsort.d#L111 Each call to mergeAt is followed by --stackLen. I could have used stackLen-- in the mergeAt statement instead, but I didn't want to rely on operator precedence for the correct behavior.
Re: opCaret to complement opDollar when specifying slices
On Saturday, 2 June 2012 at 11:49:17 UTC, Dario Schiavon wrote: Hi, I just read some old threads about opDollar and the wish to have it work for non zero-based arrays, arrays with gaps, associative arrays with non-numerical indices, and so on. It was suggested to define opDollar as the end of the array rather than the length (and perhaps rename opDollar to opEnd to reflect this interpretation), so that collection[someIndex .. $] would consistently refer to a slice from someIndex to the end of the collection (of course the keys must have a defined ordering for it to make sense). I'm just thinking, if we want to generalize slices for those cases, shouldn't we have a symmetrical operator for the first element of the array? Since the $ sign was evidently chosen to parallel the regexp syntax, why don't we add ^ to refer to the first element? This way, collection[^ .. $] would slice the entire collection, just like collection[]. Until now, ^ is only used as a binary operator, so this addition shouldn't lead to ambiguous syntax. It surely wouldn't be used as often as the opDollar, so I understand if you oppose the idea, but it would at least make the language a little more "complete". The problem I see with this, it would be a larger burden when writing generic code. Libraries would have to be written to compensate for those containers. I'd prefer that all containers are simply zero-based, unless there's a need for negative indices (i.e. pointers). I think random-access ranges may be intended to be zero-based as well.
Re: Increment / Decrement Operator Behavior
On Monday, 4 June 2012 at 20:44:42 UTC, bearophile wrote: 1) Make post/pre increments return void. This avoid those troubles. I think Go language has chosen this. This is my preferred solution. I wonder in that case, is it even worth including in the language? For me anyways, the whole point of these operators is to use them in expressions. Otherwise, why not simply write (i+=1)?
Re: One against binary searches
On Monday, 30 July 2012 at 15:40:32 UTC, bearophile wrote: This author writes very detailed analyses of low-level computational matters, that appear on Reddit. This blog post he suggests to introduce "offseted binary" or "quaternary search" instead of binary search in Phobos: http://www.pvk.ca/Blog/2012/07/30/binary-search-is-a-pathological-case-for-caches/ Bye, bearophile My stable sort makes heavy use of binary searches [1], so just for fun, I tried inserting a ternary search before the binary search. After some optimizing, I found it ideal to use ternary search on ranges larger than 8KiB (with 32KiB L1D cache) and binary search on anything less. While sorting using additional space saw no improvement, in-place sorting went from 408ms to 371ms. As well, there's a very negligible increase in the number of comparisons. [1] https://github.com/Xinok/XSort/blob/master/stablesort.d#L331
Re: One against binary searches
On Monday, 30 July 2012 at 17:20:54 UTC, bearophile wrote: Xinok: My stable sort makes heavy use of binary searches [1], so just for fun, I tried inserting a ternary search before the binary search. I think in the end he suggests to use a "offseted binary" or a "quaternary search", over both binary and ternary searches (if the array is not too much small). An offseted binary search wouldn't work in this case. The "binary search" is actually comparing elements in two adjacent ranges which are equidistant from the center, so it's impossible to align in both ranges. I also tried a quaternary search, but it was 25-30ms slower than a ternary search, albeit it was a bit faster than a binary search.
Re: One against binary searches
On Monday, 30 July 2012 at 19:52:35 UTC, bearophile wrote: Xinok: I also tried a quaternary search, but it was 25-30ms slower than a ternary search, albeit it was a bit faster than a binary search. I see. are you willing to add some of those searches here? http://dlang.org/phobos/std_range.html#SearchPolicy I've added it to my todo list. I still haven't taken the time to familiarize myself with Phobos' conventions, so I don't feel comfortable contributing anything yet.
Sorting algorithm
Hi, it's been years since I've posted here. I just wanted to share something I worked on, a new sorting algorithm. It's a variant of merge sort, but much more memory efficient with only a small loss in performance. The most similar algorithm I know of is Timsort. I had need for a stable sorting algorithm, but the performance of stable sort in Phobos is terrible. This pretty much left merge sort, which has good performance but requires O(n) space. That persuaded me to design my own sorting algorithm. Here, you can find the code, details of the algorithm, and benchmarks (introSort is the unstable sort in Phobos). http://www.neowin.net/forum/blog/422/entry-3737-sort-algorithm-complete/
Re: Sorting algorithm
On 10/7/2011 1:03 PM, Andrei Alexandrescu wrote:
On 10/7/11 11:42 AM, Xinok wrote:
Hi, it's been years since I've posted here. I just wanted to share
something I worked on, a new sorting algorithm. It's a variant of merge
sort, but much more memory efficient with only a small loss in
performance. The most similar algorithm I know of is Timsort.
I had need for a stable sorting algorithm, but the performance of stable
sort in Phobos is terrible. This pretty much left merge sort, which has
good performance but requires O(n) space. That persuaded me to design my
own sorting algorithm.
Here, you can find the code, details of the algorithm, and benchmarks
(introSort is the unstable sort in Phobos).
http://www.neowin.net/forum/blog/422/entry-3737-sort-algorithm-complete/
This is interesting. What do the numbers in the benchmark represent?
Andrei
I'll just post the code I used for benchmarking. Simply put, smaller
numbers are faster.
ubyte[16] digest;
uint[] base;
base.length = 1024 * 1024 * 16;
foreach(i, ref v; base) v = i;
randomShuffle(base);
writeln("Is sorted: ", isSorted(base));
writeln("Is length: ", base.length);
SetThreadPriority(GetCurrentThread(), THREAD_PRIORITY_TIME_CRITICAL);
long start, finish;
auto copy = base.dup;
QueryPerformanceCounter(&start);
xinokSort(copy);
QueryPerformanceCounter(&finish);
sum(digest, copy);
writeln("xinokSort: ", finish - start, "\t", digestToString(digest));
assert(isSorted(copy), "Array not sorted");
Re: Sorting algorithm
On 10/7/2011 2:20 PM, Andrei Alexandrescu wrote: On 10/7/11 12:23 PM, Xinok wrote: http://www.neowin.net/forum/blog/422/entry-3737-sort-algorithm-complete/ This is interesting. What do the numbers in the benchmark represent? Andrei I'll just post the code I used for benchmarking. Simply put, smaller numbers are faster. [snip] Thanks. It would be great if you wanted to contribute your stable sort to Phobos via a pull request. Also, which version of D are you using? I'm seeing that std.algorithm.sort (introSort) performs quite badly; for example, it's twice as slow on shuffled data against quickSort, and it also deals badly with already sorted data. Generally it does much worse than the quickSort baseline. Wonder why. Andrei I'm not familiar with the process. What all would I need to do to contribute my sort to Phobos? On another note, my sort is most efficient on random access ranges. A simple merge sort would be more practical for other data structures like linked lists. I used DMD 2.051 for those benchmarks, so I did new benchmarks using DMD 2.055. Unstable sort saw a big improvement, but stable sort still did poorly. I find it unusual since I thought stable sort was supposed to use merge sort. xinokSort: 7564654 shellSort: 8843484 quickSort: 6005074 mergeSort: 6625306 radixSort: 2837697 phobos Unstable: 5559726 phobos Stable: 113924852
Re: Sorting algorithm
On 10/7/2011 2:27 PM, Ellery Newcomer wrote: tinkered with timsort a bit a few months ago. comparing that to your sort, I get numbers like xinokSort random: 77 ascending: 0 descending: 21 timsort random: 354 ascending: 1 descending: 4 where each are sorting a 500k element array of int, times are msecs, compilation flags were -O -inline -release, sources are http://personal.utulsa.edu/~ellery-newcomer/timsort.d http://personal.utulsa.edu/~ellery-newcomer/xinokSort.d Nice job, Xinok. anyone want to try to optimize my timsort? :) The benchmark for descending is no surprise since timsort explicitly searches for runs in descending order. However, the random benchmark isn't what I expected. My sort is a bit slower than a standard merge sort, so I would expect Timsort to be faster. While part of the reason may be your code is unoptimized, it may also be the fault of a bug. I ran some more benchmarks and I found a few cases where your code failed, specifically when the data is mostly random. Just a guess, but your code may have a problem when the "runs" are too small. I also found a case when std.algorithm.sort performs poorly, under Small Shuffle + Descending. Numbers represent time taken; Smaller numbers are faster An MD5 hash is generated for each sort, to verify it was sorted correctly phoboSort is unstable std.algorithm.sort Ascending Is length: 16777216 xinokSort: 50722C8B8D3A2B4D9882ABCFC31721EF27145 shellSort: 726046 C8B8D3A2B4D9882ABCFC31721EF27145 quickSort: 943475 C8B8D3A2B4D9882ABCFC31721EF27145 mergeSort: 1778944 C8B8D3A2B4D9882ABCFC31721EF27145 radixSort: 3082901 C8B8D3A2B4D9882ABCFC31721EF27145 phoboSort: 955285 C8B8D3A2B4D9882ABCFC31721EF27145 tim Sort: 89201C8B8D3A2B4D9882ABCFC31721EF27145 Descending Is length: 16777216 xinokSort: 1916452 C8B8D3A2B4D9882ABCFC31721EF27145 shellSort: 2238446 C8B8D3A2B4D9882ABCFC31721EF27145 quickSort: 1581095 C8B8D3A2B4D9882ABCFC31721EF27145 mergeSort: 3390033 C8B8D3A2B4D9882ABCFC31721EF27145 radixSort: 3067271 C8B8D3A2B4D9882ABCFC31721EF27145 phoboSort: 1035827 C8B8D3A2B4D9882ABCFC31721EF27145 tim Sort: 240896 C8B8D3A2B4D9882ABCFC31721EF27145 Complete Shuffle Is length: 16777216 xinokSort: 7607511 C8B8D3A2B4D9882ABCFC31721EF27145 shellSort: 8814887 C8B8D3A2B4D9882ABCFC31721EF27145 quickSort: 5623837 C8B8D3A2B4D9882ABCFC31721EF27145 mergeSort: 6704733 C8B8D3A2B4D9882ABCFC31721EF27145 radixSort: 2825567 C8B8D3A2B4D9882ABCFC31721EF27145 phoboSort: 5532275 C8B8D3A2B4D9882ABCFC31721EF27145 tim Sort: 29142913 E03C4778321F69D8AD10F624E6093599 Small Shuffle (1024 pairs were picked at random and swapped) Is length: 16777216 xinokSort: 589882 C8B8D3A2B4D9882ABCFC31721EF27145 shellSort: 3651222 C8B8D3A2B4D9882ABCFC31721EF27145 quickSort: 2655391 C8B8D3A2B4D9882ABCFC31721EF27145 mergeSort: 2162840 C8B8D3A2B4D9882ABCFC31721EF27145 radixSort: 2988630 C8B8D3A2B4D9882ABCFC31721EF27145 phoboSort: 963103 C8B8D3A2B4D9882ABCFC31721EF27145 tim Sort: 6523251 C8B8D3A2B4D9882ABCFC31721EF27145 Large Shuffle (1,048,576 pairs were picked at random and swapped) Is length: 16777216 xinokSort: 1956126 C8B8D3A2B4D9882ABCFC31721EF27145 shellSort: 7617207 C8B8D3A2B4D9882ABCFC31721EF27145 quickSort: 3089674 C8B8D3A2B4D9882ABCFC31721EF27145 mergeSort: 2606200 C8B8D3A2B4D9882ABCFC31721EF27145 radixSort: 2932306 C8B8D3A2B4D9882ABCFC31721EF27145 phoboSort: 1619484 C8B8D3A2B4D9882ABCFC31721EF27145 tim Sort: 14883251 DE54E94D1A058459FEA3A80096FCBB18 Small Shuffle + Descending Is length: 16777216 xinokSort: 2288869 C8B8D3A2B4D9882ABCFC31721EF27145 shellSort: 4599417 C8B8D3A2B4D9882ABCFC31721EF27145 quickSort: 2604222 C8B8D3A2B4D9882ABCFC31721EF27145 mergeSort: 3457241 C8B8D3A2B4D9882ABCFC31721EF27145 radixSort: 3055080 C8B8D3A2B4D9882ABCFC31721EF27145 phoboSort: 261768564C8B8D3A2B4D9882ABCFC31721EF27145 tim Sort: 10149160 C8B8D3A2B4D9882ABCFC31721EF27145 Large Shuffle + Descending xinokSort: 2923813 C8B8D3A2B4D9882ABCFC31721EF27145 shellSort: 7678966 C8B8D3A2B4D9882ABCFC31721EF27145 quickSort: 3833138 C8B8D3A2B4D9882ABCFC31721EF27145 mergeSort: 3971124 C8B8D3A2B4D9882ABCFC31721EF27145 radixSort: 2941206 C8B8D3A2B4D9882ABCFC31721EF27145 phoboSort: 3749512 C8B8D3A2B4D9882ABCFC31721EF27145 tim Sort: 22709918 191BD30B3D0E52C922A7E6A16E5E63A5
Re: Sorting algorithm
On 10/7/2011 5:08 PM, Andrei Alexandrescu wrote: On 10/07/11 13:50, Xinok wrote: On 10/7/2011 2:20 PM, Andrei Alexandrescu wrote: On 10/7/11 12:23 PM, Xinok wrote: http://www.neowin.net/forum/blog/422/entry-3737-sort-algorithm-complete/ This is interesting. What do the numbers in the benchmark represent? Andrei I'll just post the code I used for benchmarking. Simply put, smaller numbers are faster. [snip] Thanks. It would be great if you wanted to contribute your stable sort to Phobos via a pull request. Also, which version of D are you using? I'm seeing that std.algorithm.sort (introSort) performs quite badly; for example, it's twice as slow on shuffled data against quickSort, and it also deals badly with already sorted data. Generally it does much worse than the quickSort baseline. Wonder why. Andrei I'm not familiar with the process. What all would I need to do to contribute my sort to Phobos? D's standard library is on github: https://github.com/D-Programming-Language/phobos. Anyone can fork it, modify it as they please, and then submit the changes for review via a so-called "pull request". Here's an example of a pull request with comments and all: https://github.com/D-Programming-Language/phobos/pull/272. There is documentation available on github.com about how to use the site. It's some work but it's time well invested - the kin of git and github are here to stay. Would anyone in the community be willing to shepherd Xinok through the first pull request? Andrei Thanks, I'll look into it when I have a little more time. If my algorithm were to be implemented in Phobos, the template arguments for std.algorithm.sort would need to be modified. For my algorithm to be stable, it requires defining two conditions, both a 'less' and 'greater'.
Re: Sorting algorithm
On 10/7/2011 12:42 PM, Xinok wrote: Hi, it's been years since I've posted here. I just wanted to share something I worked on, a new sorting algorithm. It's a variant of merge sort, but much more memory efficient with only a small loss in performance. The most similar algorithm I know of is Timsort. I had need for a stable sorting algorithm, but the performance of stable sort in Phobos is terrible. This pretty much left merge sort, which has good performance but requires O(n) space. That persuaded me to design my own sorting algorithm. Here, you can find the code, details of the algorithm, and benchmarks (introSort is the unstable sort in Phobos). http://www.neowin.net/forum/blog/422/entry-3737-sort-algorithm-complete/ To follow up on my original post, I wrote a text file which explains the algorithm in detail. The most important thing to understand is the "range swap", which I tried to explain as simply as possible. http://cl.ly/0H193k2s0G2T1A002v3I/xinokSort.txt
Re: Sorting algorithm
On 10/8/2011 11:04 AM, Andrei Alexandrescu wrote: On 10/08/11 10:01, Xinok wrote: On 10/8/2011 9:15 AM, Andrei Alexandrescu wrote: On 10/07/11 23:00, Xinok wrote: Thanks, I'll look into it when I have a little more time. Looking forward to it. If my algorithm were to be implemented in Phobos, the template arguments for std.algorithm.sort would need to be modified. For my algorithm to be stable, it requires defining two conditions, both a 'less' and 'greater'. Wouldn't swapping the argument to less work? Andrei The merge step in my algorithm is similar to Timsort, in that it can merge left to right as well as right to left. This needs two conditions to do a stable sort, 'less or equal' and 'greater or equal'. By swapping the arguments, you can only get 'greater or equal'. You're still missing 'less or equal', which is required for my algorithm to be stable. I don't understand. Say all you have is "<". Then you can do everything: a <= b is !(b < a) a > b is b < a This is an absolute classic. Probably it's negation that is missing from your assumptions? You can always negate a predicate. Andrei I actually wasn't aware you could do that O.o, although you got the operators wrong in your example. It does add overhead though. It requires two comparisons, and possibly twice the number of lookups, such as in this statement: lef[c] > rig[off - c] How about, if the greater argument is empty, then it fills it automatically with this. But also give the programmer the option to define both conditions for more efficient code.
Re: Sorting algorithm
On 10/8/2011 9:15 AM, Andrei Alexandrescu wrote:
On 10/07/11 23:00, Xinok wrote:
Thanks, I'll look into it when I have a little more time.
Looking forward to it.
If my algorithm were to be implemented in Phobos, the template arguments
for std.algorithm.sort would need to be modified. For my algorithm to be
stable, it requires defining two conditions, both a 'less' and 'greater'.
Wouldn't swapping the argument to less work?
Andrei
The merge step in my algorithm is similar to Timsort, in that it can
merge left to right as well as right to left. This needs two conditions
to do a stable sort, 'less or equal' and 'greater or equal'.
By swapping the arguments, you can only get 'greater or equal'. You're
still missing 'less or equal', which is required for my algorithm to be
stable.
It wouldn't be difficult to overload the template. When using an
unstable sort, the greater argument can be left empty.
sort!("a < b")
would simply translate to:
sort!("a < b", "", SwapStrategy.unstable)
Re: Sorting algorithm
On 10/8/2011 12:47 PM, Andrei Alexandrescu wrote: Nice writeup, but I found it quite difficult to get into. What would help is anchoring it with already known stuff (if it's not, the reader must assume it's unrelated, which makes things difficult). So it would be great if you compared and contrasted range swap with the in-place merge algorithm (e.g. http://www.sgi.com/tech/stl/inplace_merge.html), STL's stable sort (http://www.sgi.com/tech/stl/stable_sort.html) which is O(N log(N) log(N)), and possibly with std.algorithm.bringToFront. Simply presenting a stylized implementation of swap range would be helpful. I didn't mean for this text to be anything official. I just felt it was important to provide an explanation of my algorithm so others could better understand my algorithm and it's implications. That's all. There's also the issue of, "what if I'm not the first?" I couldn't find anything similar to the "range swap", but that doesn't mean it didn't already exist. Writing papers isn't my forte, I'm a self taught programmer. So if my algorithm ever gains popularity, I'll let the experts deal with it. Also there are a few oddities in the text: * "- Constant additional memory (one memory allocation per thread)" -> the parenthesis does not sustain the point. There could be one memory allocation but it might allocate a non-constant amount. I thought it was important to clarify that. My algorithm is easy to parallelize, but it does require allocating a unique block of memory for each thread. It is relatively constant as well, as it would make sense that the number of running threads matches the number of cores in the hardware. The only reason to allocate a non-constant amount is if you include the optimization I mentioned, to allocate O(n/1024) space. * All discussion about tail call optimization is unneeded. Tail calls can be converted trivially to loops, so don't mention anything. Feel free to convert to loops if needed. I think it's an issue worth addressing though. Some programmers might assume that, because it's a variant of merge sort, stack overflows won't be an issue. When I originally implemented my algorithm, I didn't use tail calls and I had problems with stack overflows on partially sorted data. So it is an issue.
Re: Sorting algorithm
On 10/8/2011 11:56 AM, Andrei Alexandrescu wrote: I think I'm missing something. Again: if you have "<" then "<=", ">", and ">=" are zero cost. What is more expensive is deciding a == b. You need to do it by saying !(a < b) && !(b < a). That's a cost worth paying because the second expression is more general - it allows you to define equivalence classes by using "<" even though the objects are not equal. Andrei nm, I got it now. >.< I can't believe I didn't know this.
Re: Sorting algorithm
On 10/8/2011 1:56 PM, Andrei Alexandrescu wrote: On 10/8/11 12:30 PM, Xinok wrote: I didn't mean for this text to be anything official. I just felt it was important to provide an explanation of my algorithm so others could better understand my algorithm and it's implications. That's all. There's also the issue of, "what if I'm not the first?" I couldn't find anything similar to the "range swap", but that doesn't mean it didn't already exist. Writing papers isn't my forte, I'm a self taught programmer. So if my algorithm ever gains popularity, I'll let the experts deal with it. My attempt was to make a few suggestions that would improve your writeup, which in turn not only helps popularity of the algorithm, but also you to hone a useful skill. Thanks for that. :) I can't update the original link, so the text is what it is. I'll look into making a better write-up of my algorithm and posting it somewhere more permanent. Also there are a few oddities in the text: * "- Constant additional memory (one memory allocation per thread)" -> the parenthesis does not sustain the point. There could be one memory allocation but it might allocate a non-constant amount. I thought it was important to clarify that. My algorithm is easy to parallelize, but it does require allocating a unique block of memory for each thread. It is relatively constant as well, as it would make sense that the number of running threads matches the number of cores in the hardware. The only reason to allocate a non-constant amount is if you include the optimization I mentioned, to allocate O(n/1024) space. Then you may want to say: * Constant additional memory and one call to an allocation routine per thread. I'll do that. I think it's an issue worth addressing though. Some programmers might assume that, because it's a variant of merge sort, stack overflows won't be an issue. When I originally implemented my algorithm, I didn't use tail calls and I had problems with stack overflows on partially sorted data. So it is an issue. No, it's not. Please think through: tail recursion IS A loop, period. (BTW I see you use simple tail recursion as opposed to the more general tail calls.) It's cut and dried. So no discussion is needed. Just mention there is no risk of stack overflow, without ever mentioning tail calls. In fact there's not even a need to mention that because otherwise the algorithm would have non-constant space complexity, which you clarify it doesn't. Take a look at the Wikipedia page for quick sort. It mentions issues with the algorithm, such as using the first element as the pivot causes worst-case behavior on sorted data, and even something I didn't know about is integer overflow when choosing a pivot. It also mentions tail calls / tail recursion five times. https://secure.wikimedia.org/wikipedia/en/wiki/Quick_sort#Implementation_issues I'll reduce talk about tail calls, I'll probably just list it under optimizations, but I'm not removing it completely. Otherwise, I'll make a note that, depending on the implementation, the range swap can result in a stack overflow, but I won't mention tail calls / tail recursion as a solution.
Re: Xinok Sort (was: Sorting algorithm)
On 10/8/2011 11:11 AM, Xinok wrote: On 10/7/2011 12:42 PM, Xinok wrote: Hi, it's been years since I've posted here. I just wanted to share something I worked on, a new sorting algorithm. It's a variant of merge sort, but much more memory efficient with only a small loss in performance. The most similar algorithm I know of is Timsort. I had need for a stable sorting algorithm, but the performance of stable sort in Phobos is terrible. This pretty much left merge sort, which has good performance but requires O(n) space. That persuaded me to design my own sorting algorithm. Here, you can find the code, details of the algorithm, and benchmarks (introSort is the unstable sort in Phobos). http://www.neowin.net/forum/blog/422/entry-3737-sort-algorithm-complete/ To follow up on my original post, I wrote a text file which explains the algorithm in detail. The most important thing to understand is the "range swap", which I tried to explain as simply as possible. http://cl.ly/0H193k2s0G2T1A002v3I/xinokSort.txt And to follow up on this post, I created a permanent page for xinok sort on Sourceforge. There's nothing new to see on this page yet, but I'll work on that in due time. https://sourceforge.net/projects/xinoksort/ My first goal is to write an implementation which I can contribute as the new stable sorting algorithm for Phobos. This includes string mixins, ranges, asserts, unittests, and anything else that is required. If anybody wants to assist me with this, I welcome the help.
Idea: Immutable blocks within functions
For me, one of the annoyances of working with immutable data is
simply initializing data. Immutable variables have to be
initialized upon declaration and cannot be modified after that
point. This is made more difficult if you have several immutable
variables to initialize in conjunction with one another
Currently, the following syntax is not allowed within functions:
immutable{ }
I propose enabling this syntax to have special usage within
functions for initializing immutable variables. Variables would
be mutable within the scope of the immutable block, and immutable
outside of that scope. That scope would be limited to the same
access restrictions as pure functions to ensure mutable
references to the data can't escape.
While something similar could be accomplished using nested
functions, they're limited to initializing one immutable variable
at a time and less efficient since they must utilize a context
pointer to access outside data. I think my idea has a nice allure
for greater simplicity and flexibility for initializing immutable
variables.
An impractical example:
void foo()
{
immutable
{
int[] arr = ...;
int[] arr2 = arr.dup;
sort(arr); // arr is still mutable
int[] arr2 = arr.dup;
reverse(arr2);
arr ~= arr2;
}
sort(arr); // Error is thrown because arr is now immutable
}
Considerations:
* Global and thread-local variables within an immutable block
would be immutable; otherwise, the control flow could re-enter
the immutable scope and change the values of those variables.
* There may be issues with reflection since the type of the
variable suddenly changes from mutable to immutable.
So what do nested immutable blocks imply? The same as having a
pure function within a pure function.
void foo()
{
immutable
{
int[] arr = ...;
immutable
{
// This statement would throw an error
int value = arr[0];
// Here, arr is still mutable.
// So like a pure function, access to outside
// mutable variables isn't allowed.
}
}
}
Re: Idea: Immutable blocks within functions
On Saturday, 7 September 2013 at 23:05:31 UTC, Peter Alexander
wrote:
On Saturday, 7 September 2013 at 22:57:40 UTC, Xinok wrote:
immutable
{
int[] arr = ...;
int[] arr2 = arr.dup;
sort(arr); // arr is still mutable
int[] arr2 = arr.dup;
reverse(arr2);
arr ~= arr2;
}
How do you stop mutable references escaping in functions called
from the immutable block?
e.g.
int* p;
void foo(ref int x) { p = &x; }
void main()
{
immutable
{
int x = 1;
foo(x);
}
*p = 0;
}
Immutable blocks would have the same restrictions as pure
functions. And like pure functions, you could only call other
pure functions. Since foo is not pure, this code wouldn't compile.
Re: Idea: Immutable blocks within functions
On Saturday, 7 September 2013 at 23:22:59 UTC, Dmitry Olshansky
wrote:
08-Sep-2013 02:57, Xinok пишет:
For me, one of the annoyances of working with immutable data
is simply
initializing data. Immutable variables have to be initialized
upon
declaration and cannot be modified after that point. This is
made more
difficult if you have several immutable variables to
initialize in
conjunction with one another
[snip]
An impractical example:
void foo()
{
immutable
{
int[] arr = ...;
int[] arr2 = arr.dup;
sort(arr); // arr is still mutable
int[] arr2 = arr.dup;
reverse(arr2);
arr ~= arr2;
}
sort(arr); // Error is thrown because arr is now immutable
}
A pure lambda can achieve the same unless, of course, purity is
out of question:
immutable arr = {
int[] arr = ...;
int[] arr2 = arr.dup;
sort(arr); // arr is still mutable
int[] arr2 = arr.dup;
reverse(arr2);
arr ~= arr2;
return arr;
} pure ();
Both arr and arr2 would exist as immutable arrays outside of that
scope. That's what I meant by, nested functions could only
initialize one immutable variable at a time, because you can only
return one value to initialize the immutable variable with. With
immutable blocks, you can initialize several immutable variables
simultaneously.
Basically even not yet completely outlined the feature already
pulls in escape analysis. Not going to fly IMHO.
They follow the same rules as pure functions. They can only
access immutable data, can only call pure functions, etc. No
need for escape analysis, no need to reinvent the wheel.
Furthermore, if the capabilities of pure functions is extended,
so is the capabilities of immutable blocks.
Re: Build Master: Scheduling
On Thursday, 14 November 2013 at 00:37:38 UTC, Tyro[17] wrote: Greetings, I have accepted the responsibility of preparing the builds for DMD and would like to engage in conversation about the way ahead. The first concern I have is about the build cycle. Presently, it is nonexistent. There is no rhyme or reason regarding when releases are produced. The v2.065 agenda (first attempt of its kind) suggests that the next release will occur sometime in March 2014. I'm of the opinion, however, that the cycle should be six months long. This particular schedule is not of my own crafting but I believe it to be sound and worthy of emulation: ... Your thoughts and concerns please. I think this is perfect. It's essentially what I would do. Ever since Google defined their six week release schedule for Chrome, people think quick release cycles are the next great thing. It was such an effective marketing strategy that Firefox had to jump the bandwagon. The truth is though, it doesn't cater well to large corporations. That's why Firefox also has ESR (Extended Support Release) for corporations which are older versions maintained for longer, only being updated for new bug and security fixes. I think the majority of people active on these forums are hardcore D enthusiasts so they're eager to have the latest and greatest. However, we're not hearing the voice of those on the outside. I'm willing to bet if we were to post this as news on Reddit, we'd be getting praise from those who aren't actively involved in the development of D. I do have a few ideas: I'm one who favors having different version numbers for beta and stable releases. Given the version number scheme that DMD follows, a simple numbering scheme to follow is odd- and even-numbered versions: odd-numbered versions, starting with 2.065, would be beta, and even-numbered versions, like 2.066, would be stable. I would define two periods during the release cycle: Early on, when it's okay to introduce new features and changes which may break code, and later on when we should be concentrating on testing, fixing bugs, and generally working towards a stable release. Finally, I think after every stable release, we should define an agenda, i.e. what are our goals for the next version? My current impression is that pull requests are incorporated into master whenever they're deemed ready. If we have a clear agenda, then we could collectively focus our efforts into a few areas for development.
Re: Worst-case performance of quickSort / getPivot
On Friday, 15 November 2013 at 21:46:26 UTC, Vladimir Panteleev wrote: ... I'm a horrible procrastinator, I should have had this fixed over a year ago, lol. Anyways, I posted a bug report about this problem long ago and a working solution has been gathering dust waiting to be implemented in Phobos. Bug report (poorly titled): http://d.puremagic.com/issues/show_bug.cgi?id=7767 Solution: https://github.com/Xinok/XSort/blob/master/unstablesort.d * It's an introsort which falls back to a bottom-up binary heap sort after so many recursions to guarantee O(n log n) performance in the worst-case. * It chooses the pivot from a median-of-five. It adds nearly zero overhead and results in a noticeable decrease in comparisons (predicate calls). I see no reason why not to add this. * My solution uses a binary insertion sort for sublists up to 32 elements long. This reduces comparisons as well but also adds a fair amount of overhead. It's about 15-20% slower when sorting an array of integers. My idea is to use this by default and specialize the linear insertion sort when the element type and predicate are known. * Regardless of these improvements, I think Timsort should be the default sorting algorithm. It's the better choice in many (most?) cases and, well, it's stable. Quick sort would still be available for those cases in which it's faster and stable sorting isn't needed. Well, it's Saturday and I have no plans. Let's see if I can't get a pull request done by the end of the day...
Re: Worst-case performance of quickSort / getPivot
On Saturday, 16 November 2013 at 20:35:21 UTC, Andrei
Alexandrescu wrote:
On 11/16/13 11:46 AM, Xinok wrote:
* Regardless of these improvements, I think Timsort should be
the
default sorting algorithm. It's the better choice in many
(most?) cases
and, well, it's stable. Quick sort would still be available
for those
cases in which it's faster and stable sorting isn't needed.
There's something fishy about a more restricted algorithm doing
better than one that's less restricted. We must improve
unstable sort, not make stable sort the default.
Andrei
Timsort is an "adaptive" sort. It's able to achieve better
performance in many cases by exploiting patterns in the data.
I decided to make a nice little test using my benchmark code here:
https://github.com/Xinok/XSort/blob/master/benchsort.d
This is the permutation I designed for the test:
static uint[] base;
base.length = 1024 * 1024;
foreach(i, ref v; base) v = i;
foreach(i; 0..1024)
{
auto rand()
{
rndGen.popFront();
return rndGen.front % base.length;
}
switch(rand() % 3)
{
// Swap two ranges of elements
case 0:
{
auto arr = [rand(), rand(), rand(), rand()];
sort(arr);
swapRanges(base[arr[0]..arr[1]], base[arr[2]..arr[3]]);
} break;
// Reverse a range of elements
case 1:
{
auto a = rand(), b = rand();
if(a > b) swap(a, b);
reverse(base[a..b]);
} break;
// Shuffle a small range of elements
case 2:
{
auto a = rand();
while(a < 1024) a = rand();
assert(a >= 1024);
randomShuffle(base[a - 1024 .. a]);
} break;
default: assert(0);
}
}
And the results (last number is predicate calls):
Current Unstable Sort 50ms 32783474
New Unstable Sort 69ms 21503542
Timsort35ms 3905887
That's why I suggest making Timsort the default sorting algorithm.
Re: Worst-case performance of quickSort / getPivot
On Sunday, 17 November 2013 at 00:56:46 UTC, Andrei Alexandrescu wrote: On 11/16/13 4:18 PM, Chris Cain wrote: You have not shown how much faster it might be (it could be only 1% faster) nor how much work it would take to discover (even an ideal pivot choice for quicksort actually cannot be as fast as Timsort on an already sorted sequence, and quicksort is not an appropriate algorithm for accepting presorted subsequences). There are well known tweaks to quicksort that make it operate well on sorted or almost sorted sequences. If you tweak for one scenario, you're only losing in other scenarios. Timsort already performs ideally in these cases, as I've demonstrated. Rather than optimizing quicksort for cases in which Timsort will still be the victor, we should optimize for those cases in which quicksort is already faster.
Re: Worst-case performance of quickSort / getPivot
On Friday, 15 November 2013 at 22:56:58 UTC, Craig Dillabaugh wrote: What are the arguments against using a randomized algorithm? (1) Sort is capable of being marked pure, depending on the type being sorted and the predicate. But choosing random pivots means introducing side effects. (2) Random pivots invoke average performance, whereas choosing the pivot from a median of N has the potential to achieve better performance on partially sorted lists (fewer reads and writes). (3) I've tested random pivots and found that choosing from a median of three or five is often the better choice.
Re: Worst-case performance of quickSort / getPivot
On Sunday, 17 November 2013 at 02:44:45 UTC, Vladimir Panteleev wrote: On Saturday, 16 November 2013 at 22:11:46 UTC, Xinok wrote: And the results (last number is predicate calls): Current Unstable Sort 50ms 32783474 New Unstable Sort 69ms 21503542 Timsort35ms 3905887 For the record, I tried both SwapStragegy options with my data (the data that got me to start this thread), and although TimSort did fewer comparisons (predicate calls), it ran about 20% slower. Could you try running a benchmark on the same data using this instead? https://github.com/Xinok/XSort/blob/master/unstablesort.d My implementation of quick sort has some odd tweaks which makes it slower in some cases, but I've never invoked worst-case behavior by accident.
Re: DIP42 - Add enum E(T) = expression; eponymous template support
On Tuesday, 25 June 2013 at 21:31:15 UTC, Walter Bright wrote:
http://wiki.dlang.org/DIP42
Reading through this thread, I already foresee a messy
specification coming along for this. Instead, I'd propose
something different that would keep the rules consistent yet have
many more applications:
template(...) declaration = ... ;
So what you would have instead:
template(T) enum E = ... ;
template(T) alias A = ... ;
There's also the possibility for simple template constraints as
well:
template(T) if(...) enum E = ... ;
Anything more complicated, such as static if, is probably best
left to the classic style:
template E(T)
{
static if(...) enum E = ... ;
else enum E = ... ;
}
A proper language comparison...
Once in a while, a thread pops up in the newsgroups pitting D against some other language. More often than not, these comparisons are flawed, non-encompassing, and uninformative. Most recently with the article comparing D with Go and Rust, the community pointed out a few flaws involving a late addition of one of the D compilers, build configurations (-noboundscheck?), and the random number generator used. Then when I think about how web browsers are compared, there are conventional measures and standard benchmarking tools (e.g. sunspider). They measure performance for javascript, rendering, HTML5, etc. They also measure startup times (hot/cold boot), memory usage, etc. Finally, there are feature comparisons, such as what HTML5 features each browser supports. These are the type of comparisons I'd like to see with programming languages. For starters, there should be standard "challenges" (algorithms and such) implemented in each language designed to measure various aspects of the language, such as sorting, number crunching, and string processing. However, rather than leave it to a single individual to implement the algorithm in several different languages, it should be left to the community to collaborate and produce an "ideal" implementation of the algorithm in their language. We could analyze factors other than performance, such as the ease of implementation (how many lines? does it use safe/unsafe features? Was it optimized using unsafe / difficult features?). What can we do about it? I propose we come together as a community, design challenges that are actually relevant and informative, and release the first implementations in D. Then we let the battle commence and invite other communities to contribute their own implementations in other languages. I think we should give it a try; start off small with just a few moderate challenges (not too simple or complex) and see where it goes from there.
Function sets as definable type
I'm not exactly sure how to explain this idea, but I'll do my
best and hopefully I don't confuse anybody...
D is one of many statically-typed languages which supports
overloading functions by parameter type and parameter count. Many
of these languages also support function pointers / delegates,
but these have the limitation of only pointing to a single
function. I've yet to encounter a language that can define a
function pointer or delegate which points to two or more
overloaded functions. To me, this is akin to how C handles arrays
which requires passing pointer and length pairs as separate
arguments.
It's possible to do this in D statically via template alias
parameters, but not dynamically via a function argument.
Likewise, you can't easily limit it to a subset of the function
overloads (two or more, but not all). I'm sure somebody could
design an elegant solution using the meta-programming abilities
of D, but I think I have a better idea...
Consider internally, such a type would be a set of two or more
functions / delegates. Internally, this is exactly what
interfaces are as well.
So that's my proposal: Allow implicitly casting a set of
overloaded functions to a compatible interface. If a function is
passed as an argument to an interface parameter, the compiler
will automatically generate a binding of that function to that
interface. I used the term "compatible interface" as obviously,
not all interfaces would work. I'd rather leave it to the
community to define what a "compatible interface" is.
What use cases are there? Well, properties are also overloaded
functions, one which gets the value, and one or more which sets
the value. There are many cases in which a container doesn't
allow handling elements as l-values, such as when opIndex and
opIndexAssign are used, and ranges don't require .front and .back
to be l-values. The result is that specialized functions must be
written to handle these cases, one example being std.algorithm
which implements a private function swapAt to handle the former
case. I've had to do this myself, implementing a function,
swapFront, to swap the front elements of two forward ranges.
A more complex case is how to handle opIndex and opIndexAssign.
Not all containers implement it as an l-value, which would
prevent such a case from working: swap(r[a], r[b]). I'm sure
there are more complex cases as well. In these situations, it
would be great if a property could be generated from any
arbitrary expression.
Special standard library functions / templates could be used to
auto-generate compatible interfaces. For example, we could define
a template which takes the get / set types as arguments and
generates an interface for it:
void foo(Property!(int, int) prop){ }
Thoughts?
Re: Function sets as definable type
On Saturday, 23 November 2013 at 18:41:23 UTC, Xinok wrote: ... Consider internally, such a type would be a set of two or more functions / delegates. Internally, this is exactly what interfaces are as well. Actually, could somebody elaborate on this for me please? With a little more thought, I realize that I'm probably wrong about this.
Re: Worst-case performance of quickSort / getPivot
On Friday, 15 November 2013 at 21:46:26 UTC, Vladimir Panteleev wrote: ... I've made a pull request to fix this issue: https://github.com/D-Programming-Language/phobos/pull/1735
Re: Probable C# 6.0 features
On Tuesday, 10 December 2013 at 18:58:01 UTC, Suliman wrote: Maybe it would be possible to get some good idea from next version of C# It's only ideas about next version, but new future maybe next: http://damieng.com/blog/2013/12/09/probable-c-6-0-features-illustrated Regarding #1 (Primary Constructors), I think the feature has limited usefulness which doesn't deserve a presence in the language and it would serve to confuse newbies who weren't aware of that feature. I prefer to consolidate existing features and make them more flexible to serve other purposes. For example, an old idea of mine is a syntax like this (assuming D had Python-style tuples): this.(x, y) = (x, y); The syntax would generate a tuple from members of this. Similarly, one could also generate arrays or dictionaries by writing this.[x, y]. Regarding #9, I see it's uses, but I wonder if it would be a good idea to implement it. My initial thoughts are that it would make grep'ing for declarations more difficult and I think it would actually make code more difficult to read. Also, due to order of evaluation, you couldn't use the variable until after the statement in which it's declared, e.g.: x + foo(out int x)
Re: alias have new syntax?
On Saturday, 18 January 2014 at 22:50:50 UTC, cmplx wrote: During the study D, I stumbled upon this design alias myInt = int; but the specification says nothing about such use alias. Is the syntax has been changed? It seems that it's documented here, albeit not clearly: http://dlang.org/declaration.html#AliasInitializer I don't see any mention of it here: http://dlang.org/declaration.html#alias I recall there being some issues with alias this = identifier, not sure if that's been resolved. Regardless, I think the documentation at the latter link needs to be updated.
Re: Why CTFE is context-sensitive?
On Monday, 27 January 2014 at 18:30:43 UTC, Pierre Talbot wrote: On Monday, 27 January 2014 at 04:07:04 UTC, Andrei Alexandrescu wrote: On 1/26/14 3:22 AM, Pierre Talbot wrote: Hi, I was wondering why CTFE is context sensitive, why don't we check every expressions and run the CTFE if it applies? Compilation would get awfully slow (and sometimes won't terminate). Andrei So it is theoretically possible? I mean if the compilation doesn't terminate, the execution won't either for at least one program input, so we can detect an infinite loop at compile-time. Moreover, isn't the same problem with context-sensitive CTFE? Pierre Just because code runs for a long time doesn't mean that it will run forever. This is known as the Halting problem [1]. We could have configurable switches to halt CTFE if it runs for more than N seconds or allocates more than N MiB. However, this still doesn't take away from the point that it would make compilation awfully slow with presumably little benefit. There are further issues in that CTFE isn't exactly stable yet (I've had it produce incorrect results in a few cases), so relying on it to produce correct, optimized code is a bad idea. I would be in favor of some "lite-CTFE" for the sake of optimization. Simply halting if the interpreter encounters a loop or function recursion should make it pretty snappy. But I think many compilers / optimizers already do this to some extent. [1] https://en.wikipedia.org/wiki/Halting_problem
Disallow null references in safe code?
I don't know where the community currently stands on non-nullable types in D, so this idea may be based on a bit of ignorance. Assuming there are some technical issues preventing non-nullable types from being implemented, I had a different idea that may be somewhat of a compromise. As you've gathered by now, it's simply to disallow nullifying references in safe code. The idea is simply that safe functions can only call other safe functions, so null references should be practically non-existant ... except that's an ideal which can't be reached with this restriction alone. There are two obvious issues: * There's no way to guarantee input is free of null references * Trusted functions may return objects with null references; it's currently not convention to avoid null references in trusted code Albeit that, I think such a restriction could be helpful in preventing bugs/crashes and writing correct code, at least until we can get non-nullable types.
Re: D as A Better C?
On Tuesday, 11 February 2014 at 19:43:00 UTC, Walter Bright wrote: What do you think? I don't do embedded programming, so take my opinion with a grain of salt... Rather than making this a compiler switch, I think it would be more beneficial to branch this off as a new project, essentially building a new compiler. Similarly, it would contain that subset of features which are practical for embedded programming and strip out the rest. Then likewise to VisualD, make it an "official" repository on GitHub. The benefit of having a separate project dedicated to embedded programming is the ability to retain a standard library without convoluting the rest of the D ecosystem. A slim standard library could be developed, mimicking (or even branched from) Phobos, but optimized for embedded systems. As DMD is updated, the changes would be merged into "embedded D", but otherwise the two would be maintained independently of one another. It wouldn't be too dissimilar to other projects like it. There are projects which add non-official extensions to other languages, such as adding a garbage collector to C/C++.
Re: D as A Better C?
On Tuesday, 11 February 2014 at 21:13:58 UTC, Peter Alexander wrote: On Tuesday, 11 February 2014 at 20:53:06 UTC, Steven Schveighoffer wrote: But the feature would be very simple to implement. You just avoid outputting any runtime type info, and avoid any compiler hooks into the runtime. There is no requirement to do anything else. The language is finished. C's standard library becomes the standard library. Who manages the releases of better C? If there is indeed a market for it, then new talent will join the community and contribute to the project. If not, then it will become a poorly maintained and unsupported feature which is eventually stripped from the compiler due to lack of use. An interesting statistic on the Linux kernel: An analysis of the Linux kernel showed 75 percent of the code from December 2008 to January 2010 was developed by programmers working for corporations, leaving about 18 percent to volunteers and 7% unclassified. https://en.wikipedia.org/wiki/Linux#Community I don't know of many people who do embedded programming for personal reasons. The majority of interest stems from corporations, not individuals. And that's where we'll find maintainers for this project.
Re: Why is int implicitly convertible to ulong?
On Sunday, 16 February 2014 at 21:35:02 UTC, Hannes Steffenhagen wrote: isImplicitlyConvertible!(int,ulong) is true. Maybe this is just me, but I get the impression that this is quite nuts. Why is an implicit conversion from a signed to an unsigned type possible? The other way round would be at least somewhat understandable if there's a static check that the values actually fit. IIRC, the way they put it is that "information is not lost," so you could always cast back to an int and get the original value. The same is not true for casting to a smaller type, e.g. int to byte, the original value may be lost.
Re: Why is int implicitly convertible to ulong?
On Monday, 17 February 2014 at 04:40:52 UTC, Jonathan M Davis wrote: On Sunday, February 16, 2014 21:35:01 Hannes Steffenhagen wrote: isImplicitlyConvertible!(int,ulong) is true. Maybe this is just me, but I get the impression that this is quite nuts. Why is an implicit conversion from a signed to an unsigned type possible? The other way round would be at least somewhat understandable if there's a static check that the values actually fit. signed to unsigned conversions (and vice versa) are implicit as are conversions from smaller integral types to larger integral types. Converting from smaller integral types to larger really doesn't cause any problems, but the signed to unsigned (or vice versa) can cause issues - one of the biggest of those being the comparison of signed and unsigned values, and IIRC, there was some discussion on making that a warning or error. However, while there are occasional problems from the conversion being implicit, if it weren't implicit, you'd be forced to cast a lot more when the signed and unsigned types interact, which would lead to messier code and could actually increase the number of bugs, because if you got in the habit of casting everywhere to get the signed to unsigned conversions to work, you'd risk accidentally doing stuff like casting a ulong to int and losing data, since the compiler would assume that you knew what you were doing with the cast. So, it's a tradeoff, and neither making the signed to unsigned (or vice versa) conversions explicit nor implicit would be without problems. Walter went with it being implicit, which matches what C does. However, unlike C, conversions that actually lose data (e.g. long -> int) do require casts so that it's easier to catch those problems. But no data is actually lost with a sign conversions, as casting it back to what it was will result in the same value (unlike with converting to a smaller integral value). Of slightly bigger concern IMHO is that bool and the character types are all treated as integral types, which is at times useful but also risks some entertaining bugs. But again, it's a matter of tradeoffs. If they required casts when interacting with integral types, then a lot more casting would be required, risking a different set of bugs. There really isn't a right answer as to whether the conversions should be implicit or explicit. It just comes down to the tradeoffs that you prefer. - Jonathan M Davis I've been bitten by signed / unsigned comparisons before, and I'm sure others have been as well. On the other hand, I can't recall any bugs that were due to an explicit cast. I can see how explicit casts might cause unexpected bugs (if the original type changes but is still a valid cast), but in my personal experience, explicit casts are safer than implicit casts. Walter decided to adopt C-style switches for D, to simplify translating code. However, implicit fall-through is notorious for causing bugs in C. So as a tradeoff, D still allows fall-through but only by explicitly writing "goto case;". We could speculate all day, but ultimately it comes down to experience of what works and what doesn't. If something is generally safe in practice, then perhaps we're better with leaving it alone. But if something is a known nuisance for causing bugs, then find a better solution.
Re: Developing Mars lander software
On Wednesday, 19 February 2014 at 00:16:03 UTC, Tolga Cakiroglu wrote: TL;DR the link though, how are they detecting that a CPU fails? An information must be passes outside of CPU to do this. The only solution comes to my mind is that main CPU changes a variable on an external memory at every step, and back up CPU checks it continuously to catch a failure immediately. But this would require about 50% of CPU's power already. While thinking about this kind of back up systems, knowing and reading that some people are really doing is really great. I'm assuming this has something to do with it: https://en.wikipedia.org/wiki/Heartbeat_%28computing%29 In clustered servers, the active node sends a continuous signal indicating it's still alive. This signal is referred to as a heartbeat. There's a standby node waiting to take over should it stop receiving this signal.
