Re: Using opDispatch as *magic* getter/setter. Possible or not?
On 3/31/11 2:32 AM, Aleksandar Ružičić wrote:
Is it possible to use opDispatch as generic getter and setter at the
same time? Something like __get() and __set() in PHP..
this is what I've tried: https://gist.github.com/895571
and I get Error: template instance opDispatch!("bar") matches more
than one template declaration, path\to\test.d(57):opDispatch(string
entryName) and path\to\test.d(66):opDispatch(string entryName)
Is mixing @property with opDispatch supposed to work at all or is
opDispatch only ment for method calls?
Or maybe there is some other way to achive what I want and I'm not
aware of it? :-)
You can't have two methods named opDispatch like that. You can do
something like this:
class Foo {
@property ref ConfigSection opDispatch(string sectionName, Args
...)(Args args)
{
static if (Args.length == 0) {} // getter
else static if (Args.length == 1) { auto value = args[0]; } // setter
}
Or, I think this will work as well:
@property ref ConfigSection opDispatch(string sectionName, Args
...)(Args args) if (Args.length == 0)
{
// getter
}
@property ref ConfigSection opDispatch(string sectionName, Args
...)(Args args) if (Args.length == 1)
{
// setter
}
}
auto foo = new Foo;
foo.bar; // works
foo.bar = 3; // currently does not work, bug
foo.bar(3); // works
--
/Jacob Carlborg
Re: template template parameter
On 03/30/2011 04:32 PM, Caligo wrote:
I have a struct that looks something like this:
struct Box(T, size_t width, size_t height){
alias width width_;
alias height height_;
//do something with a Box of different size
void Fun( B )(B b){
// using width and height of b
B.width_;
B.height_;
}
}
auto b1 = Box!(double, 2, 7)();
auto b2 = Box!(double, 3, 4)();
b1.Fun(b2);
I think the technical name for this is template template parameter.
Using the above I'm able to do what I need to do, but is there a
better way?
and should I use alias or enum?
Template template parameter means exactly that: a template parameter is
itself a template. See ContainerType below:
struct SomeContainer(T)
{
T[] elements;
}
struct SomeOtherContainer(T)
{
struct List(T)
{}
// e.g. this one may use a linked list
List!T elements;
}
struct Foo(alias ContainerType, T)
{
// Instantiate the 'template template parameter'
ContainerType!T member;
}
void main()
{
Foo!(SomeContainer, double) foo1;
Foo!(SomeOtherContainer, int) foo2;
}
ContainerType is a template parameter of Foo and is itself a template.
And 'alias' seems to work...
Ali
Re: Using opDispatch as *magic* getter/setter. Possible or not?
On 03/31/2011 02:40 AM, Aleksandar Ružičić wrote: 2011/3/31 Aleksandar Ružičić: Or maybe there is some other way to achive what I want and I'm not aware of it? :-) I know I could have used opIndex and opIndexAssign but I really want config.section.entry syntax instead of config["section"]["entry"]... Agreed. And I would really have an answer to your question, since I tried to do the same thing. Don't understand why D does not have an 'opMember' or 'opDot'. Someone knows? This would be one of the first metamethods I would introduce in a language (definitely before operator overloading). denis -- _ vita es estrany spir.wikidot.com
Using opDispatch as *magic* getter/setter. Possible or not?
Is it possible to use opDispatch as generic getter and setter at the
same time? Something like __get() and __set() in PHP..
this is what I've tried: https://gist.github.com/895571
and I get Error: template instance opDispatch!("bar") matches more
than one template declaration, path\to\test.d(57):opDispatch(string
entryName) and path\to\test.d(66):opDispatch(string entryName)
Is mixing @property with opDispatch supposed to work at all or is
opDispatch only ment for method calls?
Or maybe there is some other way to achive what I want and I'm not
aware of it? :-)
Re: Using opDispatch as *magic* getter/setter. Possible or not?
2011/3/31 Aleksandar Ružičić : > > Or maybe there is some other way to achive what I want and I'm not > aware of it? :-) > I know I could have used opIndex and opIndexAssign but I really want config.section.entry syntax instead of config["section"]["entry"]...
template template parameter
I have a struct that looks something like this:
struct Box(T, size_t width, size_t height){
alias width width_;
alias height height_;
//do something with a Box of different size
void Fun( B )(B b){
// using width and height of b
B.width_;
B.height_;
}
}
auto b1 = Box!(double, 2, 7)();
auto b2 = Box!(double, 3, 4)();
b1.Fun(b2);
I think the technical name for this is template template parameter.
Using the above I'm able to do what I need to do, but is there a
better way?
and should I use alias or enum?
Re: Contracts or Exceptions?
Jonathan M Davis: > Naturally, the executation time does vary some, but it's consistently over > 400 > times (and generally more like 450 times) more expensive to have the > exception > be thrown and caught than it is to have it not be thrown. On Windows in a benchmark I've seen thrown exceptions about as 12 times slower than Java ones. Bye, bearophile
Re: Contracts or Exceptions?
On 2011-03-30 14:05, Ali Çehreli wrote:
> On 03/30/2011 12:40 PM, Jonathan M Davis wrote:
> > On 2011-03-30 05:09, spir wrote:
> >> On 03/30/2011 05:32 AM, Ali Çehreli wrote:
> >>> On 03/29/2011 03:40 PM, Kai Meyer wrote:
> I was given two words of advice on exceptions:
> "Use exceptions for the exceptional"
> "Use exceptions only for the exceptional"
> >>>
> >>> Those advices are given by wise people: they are wise only because they
> >>> leave the definition as vague as "exceptional." :)
> >>>
> >>> And what do we do for the "not so exceptional"? Do we return error
> >>> codes? So the function implementation will be complicated and the
> >>> caller code will be complicated.
> >>>
> >>> Exceptions are a great tool to eliminate the need for error codes.
> >>>
> >>> Here is what I follow:
> >>>
> >>> - Functions have specific tasks to do; if those tasks cannot be
> >>> accomplished, the function must throw.
> >>>
> >>> In some cases the function can continue, but that behavior must be
> >>> documented. For example, if an HTML library function is responsible for
> >>> making HTML headers, of which only the levels in the range of 1-6 are
> >>> valid, that function may throw when the level is outside of the valid
> >>> range, for in that case it cannot "make an HTML header"; or it can
> >>> document that if the level is outside of the range, 1 or 6 will be
> >>> used.
> >>>
> >>> - Catch exceptions only when there is a sensible thing to do at that
> >>> level: log an error, skip that operation, go back to the user with an
> >>> error code, take corrective action, etc.
> >>>
> >>> Disclaimer: That is what I follow in C++ code. I don't have experience
> >>> with exception safety in D. I don't know issues that may be specific to
> >>> D.
> >>
> >> These are sensible and well expressed guidelines, thank you.
> >> In other languages, I happened to use exceptions as a // channel for
> >> side-information (eg 'nomatch' for a matching func), but in D I realised
> >> how 'exceptionnally' (!) costly throwing& catching exceptions is, so
> >> that I do not do it anymore. No idea though whether this exceptional
> >> cost is perticular to D.
> >
> > I'd have to measure it in C++, Java, and C#, but I'm pretty sure that D's
> > is at least a lot slower than Java. Java uses exceptions all over the
> > place, and it works quite well overall IMHO, but I never got the
> > impression that there was any kind of major overhead for exceptions
> > (though obviously there's going to be at least _some_ performance hit
> > for derailing the thread of execution like that). In D however, it seems
> > to be significant. As I've been reworking std.datetime's unit tests,
> > I've found that I've had to be very careful about how often I use
> > assertThrown, or there is a _major_ increase in how long the unit tests
> > take to execute. While changing some tests, I had some loops which
> > included assertThrown. It turns out that with assertThrown, they'd be
> > 10+ seconds long, whereas without, they'd be a matter of milliseconds.
> > So, the performance of exceptions in D is quite poor and while it
> > probably doesn't matter all that much for normal code execution, it's
> > definitely annoying for heavy unit testing which is validating that
> > functions throw when they're supposed to throw.
> >
> > As a test, on my machine, this program
> >
> > ===
> > import std.datetime;
> > import std.exception;
> > import std.stdio;
> >
> > void main()
> > {
> >
> > auto date = Date(2011, 5, 7);
> > {
> >
> > auto curr = Clock.currTime();
> > assertNotThown!DateTimeException(date.day = 29);
> > writeln(curr - Clock.currTime());
> >
> > }
> >
> > {
> >
> > auto curr = Clock.currTime();
> > assertThrown!DateTimeException(date.day = 32);
> > writeln(curr - Clock.currTime());
> >
> > }
> >
> > }
> > ===
> >
> > prints out this
> >
> > -1 μs and -4 hnsecs
> > -637 μs and -7 hnsecs
>
> That's too much. :) I get consistent results with -O on a 64-bit Ubuntu:
>
> -1 μs and -9 hnsecs
> -832 μs and -9 hnsecs
>
> But with the addition of the -m64 flag, it's more than 4 times faster:
>
> -1 μs
> -175 μs and -4 hnsecs
>
> Still not good. :-/
LOL. And I just realized that I did those subtractions backwards. They're
negative where they should be positive. Oh well. The numbers are still clear,
and I was in a hurry when I wrote the test code.
- Jonathan M Davis
Re: Contracts or Exceptions?
On 03/30/2011 12:40 PM, Jonathan M Davis wrote:
On 2011-03-30 05:09, spir wrote:
On 03/30/2011 05:32 AM, Ali Çehreli wrote:
On 03/29/2011 03:40 PM, Kai Meyer wrote:
I was given two words of advice on exceptions:
"Use exceptions for the exceptional"
"Use exceptions only for the exceptional"
Those advices are given by wise people: they are wise only because they
leave the definition as vague as "exceptional." :)
And what do we do for the "not so exceptional"? Do we return error codes?
So the function implementation will be complicated and the caller code
will be complicated.
Exceptions are a great tool to eliminate the need for error codes.
Here is what I follow:
- Functions have specific tasks to do; if those tasks cannot be
accomplished, the function must throw.
In some cases the function can continue, but that behavior must be
documented. For example, if an HTML library function is responsible for
making HTML headers, of which only the levels in the range of 1-6 are
valid, that function may throw when the level is outside of the valid
range, for in that case it cannot "make an HTML header"; or it can
document that if the level is outside of the range, 1 or 6 will be used.
- Catch exceptions only when there is a sensible thing to do at that
level: log an error, skip that operation, go back to the user with an
error code, take corrective action, etc.
Disclaimer: That is what I follow in C++ code. I don't have experience
with exception safety in D. I don't know issues that may be specific to
D.
These are sensible and well expressed guidelines, thank you.
In other languages, I happened to use exceptions as a // channel for
side-information (eg 'nomatch' for a matching func), but in D I realised
how 'exceptionnally' (!) costly throwing& catching exceptions is, so that
I do not do it anymore. No idea though whether this exceptional cost is
perticular to D.
I'd have to measure it in C++, Java, and C#, but I'm pretty sure that D's is
at least a lot slower than Java. Java uses exceptions all over the place, and
it works quite well overall IMHO, but I never got the impression that there
was any kind of major overhead for exceptions (though obviously there's going
to be at least _some_ performance hit for derailing the thread of execution
like that). In D however, it seems to be significant. As I've been reworking
std.datetime's unit tests, I've found that I've had to be very careful about
how often I use assertThrown, or there is a _major_ increase in how long the
unit tests take to execute. While changing some tests, I had some loops which
included assertThrown. It turns out that with assertThrown, they'd be 10+
seconds long, whereas without, they'd be a matter of milliseconds. So, the
performance of exceptions in D is quite poor and while it probably doesn't
matter all that much for normal code execution, it's definitely annoying for
heavy unit testing which is validating that functions throw when they're
supposed to throw.
As a test, on my machine, this program
===
import std.datetime;
import std.exception;
import std.stdio;
void main()
{
auto date = Date(2011, 5, 7);
{
auto curr = Clock.currTime();
assertNotThown!DateTimeException(date.day = 29);
writeln(curr - Clock.currTime());
}
{
auto curr = Clock.currTime();
assertThrown!DateTimeException(date.day = 32);
writeln(curr - Clock.currTime());
}
}
===
prints out this
-1 μs and -4 hnsecs
-637 μs and -7 hnsecs
That's too much. :) I get consistent results with -O on a 64-bit Ubuntu:
-1 μs and -9 hnsecs
-832 μs and -9 hnsecs
But with the addition of the -m64 flag, it's more than 4 times faster:
-1 μs
-175 μs and -4 hnsecs
Still not good. :-/
Ali
Naturally, the executation time does vary some, but it's consistently over 400
times (and generally more like 450 times) more expensive to have the exception
be thrown and caught than it is to have it not be thrown. That's _really_
expensive. I'd be stunned if Java's or C#'s were that bad, but I'd have to go
and test it. C++'s might be, but given how much Java and C# use exceptions, it
would ludicrous if either of them had that kind of overhead for exceptions.
- Jonathan M Davis
Re: Contracts or Exceptions?
On 2011-03-30 05:09, spir wrote:
> On 03/30/2011 05:32 AM, Ali Çehreli wrote:
> > On 03/29/2011 03:40 PM, Kai Meyer wrote:
> >> I was given two words of advice on exceptions:
> >> "Use exceptions for the exceptional"
> >> "Use exceptions only for the exceptional"
> >
> > Those advices are given by wise people: they are wise only because they
> > leave the definition as vague as "exceptional." :)
> >
> > And what do we do for the "not so exceptional"? Do we return error codes?
> > So the function implementation will be complicated and the caller code
> > will be complicated.
> >
> > Exceptions are a great tool to eliminate the need for error codes.
> >
> > Here is what I follow:
> >
> > - Functions have specific tasks to do; if those tasks cannot be
> > accomplished, the function must throw.
> >
> > In some cases the function can continue, but that behavior must be
> > documented. For example, if an HTML library function is responsible for
> > making HTML headers, of which only the levels in the range of 1-6 are
> > valid, that function may throw when the level is outside of the valid
> > range, for in that case it cannot "make an HTML header"; or it can
> > document that if the level is outside of the range, 1 or 6 will be used.
> >
> > - Catch exceptions only when there is a sensible thing to do at that
> > level: log an error, skip that operation, go back to the user with an
> > error code, take corrective action, etc.
> >
> > Disclaimer: That is what I follow in C++ code. I don't have experience
> > with exception safety in D. I don't know issues that may be specific to
> > D.
>
> These are sensible and well expressed guidelines, thank you.
> In other languages, I happened to use exceptions as a // channel for
> side-information (eg 'nomatch' for a matching func), but in D I realised
> how 'exceptionnally' (!) costly throwing & catching exceptions is, so that
> I do not do it anymore. No idea though whether this exceptional cost is
> perticular to D.
I'd have to measure it in C++, Java, and C#, but I'm pretty sure that D's is
at least a lot slower than Java. Java uses exceptions all over the place, and
it works quite well overall IMHO, but I never got the impression that there
was any kind of major overhead for exceptions (though obviously there's going
to be at least _some_ performance hit for derailing the thread of execution
like that). In D however, it seems to be significant. As I've been reworking
std.datetime's unit tests, I've found that I've had to be very careful about
how often I use assertThrown, or there is a _major_ increase in how long the
unit tests take to execute. While changing some tests, I had some loops which
included assertThrown. It turns out that with assertThrown, they'd be 10+
seconds long, whereas without, they'd be a matter of milliseconds. So, the
performance of exceptions in D is quite poor and while it probably doesn't
matter all that much for normal code execution, it's definitely annoying for
heavy unit testing which is validating that functions throw when they're
supposed to throw.
As a test, on my machine, this program
===
import std.datetime;
import std.exception;
import std.stdio;
void main()
{
auto date = Date(2011, 5, 7);
{
auto curr = Clock.currTime();
assertNotThown!DateTimeException(date.day = 29);
writeln(curr - Clock.currTime());
}
{
auto curr = Clock.currTime();
assertThrown!DateTimeException(date.day = 32);
writeln(curr - Clock.currTime());
}
}
===
prints out this
-1 μs and -4 hnsecs
-637 μs and -7 hnsecs
Naturally, the executation time does vary some, but it's consistently over 400
times (and generally more like 450 times) more expensive to have the exception
be thrown and caught than it is to have it not be thrown. That's _really_
expensive. I'd be stunned if Java's or C#'s were that bad, but I'd have to go
and test it. C++'s might be, but given how much Java and C# use exceptions, it
would ludicrous if either of them had that kind of overhead for exceptions.
- Jonathan M Davis
Re: Can I use a delegate as a template parameter? (Issue 2962?)
On Wed, 30 Mar 2011 14:07:51 +0200, Magnus Lie Hetland
wrote:
A while ago, I wrote something like this:
void C(alias foo)() {
void bar() {
foo();
}
bar();
}
void B(T)(uint x=2) {
uint foo() {
return x;
}
C!foo();
}
Also, aside from the erratic DMD behavior, I'm guessing my code might be
invalid, and shouldn't have worked in the first place. After all, x is a
run-time argument, and is part of foo, which functions as a compile-time
argument. I mean, the set-up *could* work (and, in fact, generally seems
to do so), but it might be a bit problematic?
Don't worry, that's supposed to work.
--
Simen
Re: Contracts or Exceptions?
On 03/30/2011 08:42 AM, Kai Meyer wrote:
> we were talking about what sort of things you can do to
> increase performance
Sorry to change the topic. :) I am fortunate that what I currently work
on does not require more than being careful about not using the wrong
algorithms and data structures.
> if (good data)
> do work
> else
> report "can't do work"
That is helpful as long as the data can be checked up front, but we
can't always be sure:
if (file_exists()) {
use_file(); // <-- the file may not exist
or
if (server_is_up()) {
talk_to_server(); // <-- the server may not be up
> Would be faster than:
>
> try
> do work
> catch
> report "can't do work"
Apparently that's what Denis' (spir) measurements show as well and
that's very unfortunate. I would like to put that slowness under the
"quality of implementation" category. Although, it's well known that
exception handling has been slow (e.g. in C++) in general too.
(Note: I heard that scope(failure) is lowered to a try-catch block by
the compiler; so it should be slow too.)
If exceptions are inherently slow, that must be because they provide
more than what we compare them against. A good example is comparing old
features of C to C++. Some people claim that calling virtual functions
is slow due to jumping off the vtbl. Correct, but let's not forget that
achieving the same in C would be slow too.
Your examples do have such a feature difference: the code that uses the
try-catch block will always execute the code in the catch clause. On the
other hand, the code that checks the data before hand may not report
"can't do work", as "do work" may get complicated in the future and may
call a function that may throw directly or indirectly. And suddenly the
function doesn't work anymore and the changes that we've made are
detached from this function. Bad bug! :)
We may argue that exceptions should not exist in D (or C++) but they are
so helpful (hey, I know we all know these :)):
- exceptions make it impossible (or very hard) to continue with bad
program state
- they allow functions to return objects by freeing the return value
from always being an error code (return values are preferable to side
effects)
- they eliminate boiler plate error management lines (To complicate
matters, when a function needs to do cleanup after an error, it may call
other functions that may return more error codes. We must be careful not
to change the value of the original error code variable.)
- they result in less lines of code (bugs live in lines of code :))
I would like to show two functions written in C and C++. To my
knowledge, they are well written and don't have any resource leaks:
// a C function
int bar_C(Resource ** in_out)
{
int err = 0;
Resource * r0 = NULL;
Resource * r1 = NULL;
err = allocate_resource(&r0);
if (err) goto finally;
err = allocate_resource(&r1);
if (err) goto finally;
/* ... use r0 and r1 here ... */
if (err) goto finally;
/* transfer ownership */
*in_out = r0;
r0 = NULL;
finally:
deallocate_resource(&r1);
deallocate_resource(&r0);
return err;
}
// The equivalent C++ function
Resource bar_CPP()
{
Resource r0(/* ... */);
Resource r1(/* ... */);
/* ... use r0 and r1 here ... */
/* transfer ownership */
return r0;
}
Of course the latter takes advantage of other features of C++, but it
also shows that there is no explicit error management when the code
relies on exceptions. bar_CPP() just does what it is supposed to do.
Yes, there may be errors but bar_CPP() doesn't care. And the callers may
or may not catch the errors, but bar_CPP() doesn't care.
> I'm not sure D's exceptions are much different than C++'s.
Yeah, it must be the same as what Digital Mars C++ compiler uses.
(Except, D also has the 'finally' clause.)
In summary: I hope I will never go back to pass-the-error-code style of
coding.
Ali
Re: Contracts or Exceptions?
On 03/29/2011 09:32 PM, Ali Çehreli wrote: On 03/29/2011 03:40 PM, Kai Meyer wrote: > I was given two words of advice on exceptions: > "Use exceptions for the exceptional" > "Use exceptions only for the exceptional" Those advices are given by wise people: they are wise only because they leave the definition as vague as "exceptional." :) Ya, now that I'm thinking about it a little more, we were talking about what sort of things you can do to increase performance. This was actually pretty far down the list, after considering things like profiling, improving algorithms, using built-in types instead of classes, ect. Exceptions are a little more expensive than condition statements. And what do we do for the "not so exceptional"? Do we return error codes? So the function implementation will be complicated and the caller code will be complicated. You're right. I would consider those complications only if the optimisation I'm after justifies them. For example, if our profiler indicates that the function is running slowly due to handling a lot of exceptions (which probably won't be the first thing the profiler finds is running slow), we could use conditional statements to speed things up a bit. if (good data) do work else report "can't do work" Would be faster than: try do work catch report "can't do work" I'll also add that the same person who gave me this advice also likes to say "Premature optimisation is the root of all evil." Exceptions are a great tool to eliminate the need for error codes. Here is what I follow: - Functions have specific tasks to do; if those tasks cannot be accomplished, the function must throw. In some cases the function can continue, but that behavior must be documented. For example, if an HTML library function is responsible for making HTML headers, of which only the levels in the range of 1-6 are valid, that function may throw when the level is outside of the valid range, for in that case it cannot "make an HTML header"; or it can document that if the level is outside of the range, 1 or 6 will be used. - Catch exceptions only when there is a sensible thing to do at that level: log an error, skip that operation, go back to the user with an error code, take corrective action, etc. Disclaimer: That is what I follow in C++ code. I don't have experience with exception safety in D. I don't know issues that may be specific to D. Ali Thanks for your insight Ali :) I'm not sure D's exceptions are much different than C++'s. I think you're right on.
Re: Contracts or Exceptions?
On 03/30/2011 08:25 AM, Kagamin wrote: Kai Meyer Wrote: do all the checking before hand. Arrays are a good example. When not in -release mode, array boundaries are checked upon every access to the array, and an exception is thrown if access goes out of bounds. In -release mode, if you go out of bounds you get a segfault. No, you get a remote root vulnerability. Sure, but the point is that arrays can be used in a way that performs as fast as possible, therefore it becomes the programmer's job to ensure that all access to the array is within bounds, which is faster than making the array check itself every time.
Re: Memory usage of AAs?
On 03/30/2011 03:31 PM, Steven Schveighoffer wrote:
On Tue, 29 Mar 2011 22:20:05 -0400, Nick Sabalausky wrote:
"spir" wrote in message
news:mailman.2909.1301443345.4748.digitalmars-d-le...@puremagic.com...
On 03/30/2011 01:24 AM, Nick Sabalausky wrote:
My understanding of hash tables is that they allocate a fixed size array
and
map keys to indicies within the range 0..predefined_length_of_the_AA.
So I've been wondering, how many elements do D's built-in AAs have? And
what's the content of each one, just a single pointer?
Each element is a data structure, often called bucket (typically a link
list), storing (key:value) pairs for which the key, once hashed and
modulo-ed, maps to the given index. That's why the famous O(1) lookup time
for hash tables is very theoretic: the constant part holds average time
for hashing which is very variable, plus another average time for linearly
traversing the bucket. The latter part depends on table load factor (=
number of elements / number of buckets) and proper statistical repartition
of keys into buckets.
The key (!) points are finding a good hash func to "linearize" said
repartition (which depends on actual key-data domain, not only on their
type...), but better ones rapidly eat much time (ones used in practice are
rather simple & fast); and finding optimal load factor, and growth scheme.
In practice, all of this tends to make hash tables an implementation
nightmare (for me). I'd love to find practicle alternatives, but efficient
binary trees also are complex and even more depend on kind of keys, I
guess.
Right, I know that, but that's not what I was asking. Take this hypothetical
implementation:
struct Bucket(TKey, TVal)
{
...
}
enum hashTableSize = ...;
struct Hash(TKey, TVal)
{
Bucket!(TKey, TVal)[hashTableSize] data;
TVal get(TKey key) { ... }
void set(TKey key, TVal value) { ... }
}
I assume that D's AA are something at least vaguely like that. My questions
are:
1. What does D use for "hashTableSize"? Or does "hashTableSize" vary? If it
varies, what's a typical rough ballpark size? (And just out of curiosity, if
it varies, is it decided at compile-time, or does it change even at
runtime?)
It varies. The hash table size is not constant, the load factor is. The load
factor is the number of elements in the hash divided by the number of buckets.
You never want to fill up all the spaces, because the more full you get, the
more chances for collisions there are. Essentially, the tricky part about
hashing is what to do about collisions (two elements are different, but go in
the same bucket).
So what happens is when the load factor exceeds a predefined constant (e.g. in
dcollections the load factor defaults to .75), the table "rehashes", or
increases (usually logarithmically) the size of the array, and re-inserts all
its elements.
I believe there is a minimum array size, and things are increased from there. I
think also you can do a manual "rehash" which should adjust the size of the
array to match a certain load factor (below the maximum).
Yes, there is a rehash method.
In some implementations, hashes will even shrink when the load factor goes
below a minimum (dcollections does not do this to avoid invalidating ranges).
There are a million different ways to implement the basic hash. The most
complex part though, is usually the collision handling. In my algo book, there
are at least 3 ways to handle collisions, and I think there are countless more.
If you look up hashing on wikipedia, you'll get a much better explanation.
2. What is "sizeof(Bucket(TKey, TVal))"? And I mean the shallow size, not
deep size. Is it dependent on TKey or TVal? Or is it just simply a pointer
to the start of a linked list (and therefore "sizeof(size_t)")?
Here is the AA implementation:
https://github.com/D-Programming-Language/druntime/blob/master/src/rt/aaA.d
From that page, you can see that AA is your bucket (note this is runtime
stuff, so there are no templates), and BB is your Hash struct. It looks like BB
has an array of AA pointers.
IIRC, this is because buckets are (minimal) link lists. Cells holding key:value
are list nodes.
-Steve
--
_
vita es estrany
spir.wikidot.com
Re: Contracts or Exceptions?
Kai Meyer Wrote: > do all the checking before hand. Arrays are a good example. When not in > -release mode, array boundaries are checked upon every access to the > array, and an exception is thrown if access goes out of bounds. In > -release mode, if you go out of bounds you get a segfault. No, you get a remote root vulnerability.
Re: Contracts or Exceptions?
Mike Linford Wrote: > Hello, > > So I'm writing a function for a library. It takes a struct as an > argument. The struct's fields can't just be any old values, though. The > function won't work if some of the fields are weird. It could return an > erroneous value, or even crash. > > The thing is, though, that I can't tell whether the best approach is to > use an in-contract or throw an exception if it doesn't pass my test. What > would you guys recommend? Error (like AssertError) is intended to be irrecoverable like out of memory or stack overflow, Exception is intended to be catchable.
Re: Memory usage of AAs?
On Tue, 29 Mar 2011 22:20:05 -0400, Nick Sabalausky wrote:
"spir" wrote in message
news:mailman.2909.1301443345.4748.digitalmars-d-le...@puremagic.com...
On 03/30/2011 01:24 AM, Nick Sabalausky wrote:
My understanding of hash tables is that they allocate a fixed size
array
and
map keys to indicies within the range 0..predefined_length_of_the_AA.
So I've been wondering, how many elements do D's built-in AAs have? And
what's the content of each one, just a single pointer?
Each element is a data structure, often called bucket (typically a link
list), storing (key:value) pairs for which the key, once hashed and
modulo-ed, maps to the given index. That's why the famous O(1) lookup
time
for hash tables is very theoretic: the constant part holds average time
for hashing which is very variable, plus another average time for
linearly
traversing the bucket. The latter part depends on table load factor (=
number of elements / number of buckets) and proper statistical
repartition
of keys into buckets.
The key (!) points are finding a good hash func to "linearize" said
repartition (which depends on actual key-data domain, not only on their
type...), but better ones rapidly eat much time (ones used in practice
are
rather simple & fast); and finding optimal load factor, and growth
scheme.
In practice, all of this tends to make hash tables an implementation
nightmare (for me). I'd love to find practicle alternatives, but
efficient
binary trees also are complex and even more depend on kind of keys, I
guess.
Right, I know that, but that's not what I was asking. Take this
hypothetical
implementation:
struct Bucket(TKey, TVal)
{
...
}
enum hashTableSize = ...;
struct Hash(TKey, TVal)
{
Bucket!(TKey, TVal)[hashTableSize] data;
TVal get(TKey key) { ... }
void set(TKey key, TVal value) { ... }
}
I assume that D's AA are something at least vaguely like that. My
questions
are:
1. What does D use for "hashTableSize"? Or does "hashTableSize" vary? If
it
varies, what's a typical rough ballpark size? (And just out of
curiosity, if
it varies, is it decided at compile-time, or does it change even at
runtime?)
It varies. The hash table size is not constant, the load factor is. The
load factor is the number of elements in the hash divided by the number of
buckets. You never want to fill up all the spaces, because the more full
you get, the more chances for collisions there are. Essentially, the
tricky part about hashing is what to do about collisions (two elements are
different, but go in the same bucket).
So what happens is when the load factor exceeds a predefined constant
(e.g. in dcollections the load factor defaults to .75), the table
"rehashes", or increases (usually logarithmically) the size of the array,
and re-inserts all its elements.
I believe there is a minimum array size, and things are increased from
there. I think also you can do a manual "rehash" which should adjust the
size of the array to match a certain load factor (below the maximum).
In some implementations, hashes will even shrink when the load factor goes
below a minimum (dcollections does not do this to avoid invalidating
ranges). There are a million different ways to implement the basic hash.
The most complex part though, is usually the collision handling. In my
algo book, there are at least 3 ways to handle collisions, and I think
there are countless more. If you look up hashing on wikipedia, you'll get
a much better explanation.
2. What is "sizeof(Bucket(TKey, TVal))"? And I mean the shallow size, not
deep size. Is it dependent on TKey or TVal? Or is it just simply a
pointer
to the start of a linked list (and therefore "sizeof(size_t)")?
Here is the AA implementation:
https://github.com/D-Programming-Language/druntime/blob/master/src/rt/aaA.d
From that page, you can see that AA is your bucket (note this is runtime
stuff, so there are no templates), and BB is your Hash struct. It looks
like BB has an array of AA pointers.
-Steve
Can I use a delegate as a template parameter? (Issue 2962?)
A while ago, I wrote something like this:
void C(alias foo)() {
void bar() {
foo();
}
bar();
}
void B(T)(uint x=2) {
uint foo() {
return x;
}
C!foo();
}
It worked well, so I didn't think any more about it. Then suddenly, I
started getting the following error:
./path/to/foo.d(12): Error: function path.to.foo.B!(real).B compiler
error, parameter 'x', bugzilla 2962?
Assertion failed: (0), function toObjFile, file glue.c, line 729.
This only happens when I compile with -inline, and error disappears if
I make certain really minor changes to which modules are imported where
(currently 17 basically empty modules are involved in the minimal case
I've been able to produce), so the compiler behavior seems like a bug.
As Don says in a comment to 2962, "This is really tough, it's an
order-of-evaluation issue.
When generating the code for a template, which has a local variable as an alias
parameter, the alias parameter MUST be created before the code for
template is."
The error message also seems different from that of issue 2962 (which
DMD dutifully points me toward :), so I'm uncertain about whether it's
the same issue. What does it look like to you guys?
Also, aside from the erratic DMD behavior, I'm guessing my code might
be invalid, and shouldn't have worked in the first place. After all, x
is a run-time argument, and is part of foo, which functions as a
compile-time argument. I mean, the set-up *could* work (and, in fact,
generally seems to do so), but it might be a bit problematic?
This way of doing it seems like the most practical for my current use,
though... (I.e., I'd like foo to be inline-able, and have access to x.)
--
Magnus Lie Hetland
http://hetland.org
Re: Contracts or Exceptions?
On 03/30/2011 05:32 AM, Ali Çehreli wrote: On 03/29/2011 03:40 PM, Kai Meyer wrote: I was given two words of advice on exceptions: "Use exceptions for the exceptional" "Use exceptions only for the exceptional" Those advices are given by wise people: they are wise only because they leave the definition as vague as "exceptional." :) And what do we do for the "not so exceptional"? Do we return error codes? So the function implementation will be complicated and the caller code will be complicated. Exceptions are a great tool to eliminate the need for error codes. Here is what I follow: - Functions have specific tasks to do; if those tasks cannot be accomplished, the function must throw. In some cases the function can continue, but that behavior must be documented. For example, if an HTML library function is responsible for making HTML headers, of which only the levels in the range of 1-6 are valid, that function may throw when the level is outside of the valid range, for in that case it cannot "make an HTML header"; or it can document that if the level is outside of the range, 1 or 6 will be used. - Catch exceptions only when there is a sensible thing to do at that level: log an error, skip that operation, go back to the user with an error code, take corrective action, etc. Disclaimer: That is what I follow in C++ code. I don't have experience with exception safety in D. I don't know issues that may be specific to D. These are sensible and well expressed guidelines, thank you. In other languages, I happened to use exceptions as a // channel for side-information (eg 'nomatch' for a matching func), but in D I realised how 'exceptionnally' (!) costly throwing & catching exceptions is, so that I do not do it anymore. No idea though whether this exceptional cost is perticular to D. Denis -- _ vita es estrany spir.wikidot.com
