On Saturday, 23 April 2016 at 09:13:01 UTC, Johan Engelen wrote:
Well, this 140k list has a removal very early on, so the linear
search is going to happen >100k times from then on ;)
No – only for searching the particular removed item (or other
false positives due to hash collisions).
—
On Friday, 22 April 2016 at 23:33:24 UTC, Walter Bright wrote:
On 4/22/2016 3:07 PM, David Nadlinger wrote:
On Friday, 22 April 2016 at 21:48:09 UTC, Walter Bright wrote:
Why not just use a hash table? D's builtin one?
Apparently, some parts rely on the insertion order, although
I'm not
On Friday, 22 April 2016 at 22:37:49 UTC, David Nadlinger wrote:
On Friday, 22 April 2016 at 21:38:41 UTC, Johan Engelen wrote:
I don't understand exactly what you mean; do you propose to
[…] do a linear search when the shadow data structure says the
item is present?
That's the idea. As long
On Friday, 22 April 2016 at 23:49:22 UTC, Walter Bright wrote:
BTW, this looks like a particularly bad piece of engineering.
The trouble is, it saves an index to the member, then does a
bunch of semantic processing, then deletes what is on that
index. But what if the members[] in the meantime
On 4/15/2016 11:33 AM, Johan Engelen wrote:
The culprit is the linear search at the end of appendToModuleMember, because the
members list with Dsymbols gets pretty large (50k+ members).
https://github.com/D-Programming-Language/dmd/blob/master/src/dtemplate.d#L8012-L8026
On 4/22/2016 4:31 PM, Walter Bright wrote:
On 4/22/2016 3:16 PM, David Nadlinger wrote:
One of them is
https://github.com/dlang/dmd/blob/5ea445c68451152d43595c9de4797b6ec1e4f57d/src/dtemplate.d#L6503,
I think.
Definitely one.
BTW, this looks like a particularly bad piece of engineering.
On 4/22/2016 3:07 PM, David Nadlinger wrote:
On Friday, 22 April 2016 at 21:48:09 UTC, Walter Bright wrote:
Why not just use a hash table? D's builtin one?
Apparently, some parts rely on the insertion order, although I'm not convinced
they should. Module::importAll is one of them, but in a
On 4/22/2016 3:16 PM, David Nadlinger wrote:
One of them is
https://github.com/dlang/dmd/blob/5ea445c68451152d43595c9de4797b6ec1e4f57d/src/dtemplate.d#L6503,
I think.
Definitely one.
On Friday, 22 April 2016 at 21:38:41 UTC, Johan Engelen wrote:
I don't understand exactly what you mean; do you propose to […]
do a linear search when the shadow data structure says the item
is present?
That's the idea. As long as you can reduce the need to do a full
linear search by, say, 1
On Friday, 22 April 2016 at 22:10:47 UTC, Walter Bright wrote:
On 4/22/2016 2:38 PM, Johan Engelen wrote:
I don't understand exactly what you mean; do you propose to
resort to linear
search after a removal happened? Or only do a linear search
when the shadow data
structure says the item is
On 4/22/2016 2:38 PM, Johan Engelen wrote:
I don't understand exactly what you mean; do you propose to resort to linear
search after a removal happened? Or only do a linear search when the shadow data
structure says the item is present?
I don't know how often removals happen, but for the 140k
On Friday, 22 April 2016 at 21:48:09 UTC, Walter Bright wrote:
Why not just use a hash table? D's builtin one?
Apparently, some parts rely on the insertion order, although I'm
not convinced they should. Module::importAll is one of them, but
in a way that's trivial to avoid. I didn't check
On 4/22/2016 11:55 AM, David Nadlinger wrote:
On Friday, 22 April 2016 at 18:51:57 UTC, David Nadlinger wrote:
As long as elements are not removed too frequently (what do your numbers
say?), the performance impact of doing a full linear search in those cases
shouldn't be too bad.
Note that a
On Friday, 22 April 2016 at 18:51:57 UTC, David Nadlinger wrote:
On Saturday, 16 April 2016 at 13:58:28 UTC, Johan Engelen wrote:
In rare cases, symbols are removed from the members list, so
the shadow data structure needs the ability to delete elements.
Bloom filters can have false
On Friday, 15 April 2016 at 18:33:44 UTC, Johan Engelen wrote:
I'm thinking about removing the old array all-together.
My question is: is it essential to keep an ordered list? (I see
a `.shift(...)` call on the array, to put something in first
position. If so, could that be solved by having
On Friday, 22 April 2016 at 18:51:57 UTC, David Nadlinger wrote:
As long as elements are not removed too frequently (what do
your numbers say?), the performance impact of doing a full
linear search in those cases shouldn't be too bad.
Note that a (properly tuned) probabilistic data structure
On Saturday, 16 April 2016 at 13:58:28 UTC, Johan Engelen wrote:
On Friday, 15 April 2016 at 19:32:46 UTC, David Nadlinger wrote:
Another "quick fix" if we have to keep the order would be to
add a Bloom filter/… on the side to eliminate most array
searches.
In rare cases, symbols are removed
On Friday, 15 April 2016 at 19:32:46 UTC, David Nadlinger wrote:
Another "quick fix" if we have to keep the order would be to
add a Bloom filter/… on the side to eliminate most array
searches.
In rare cases, symbols are removed from the members list, so the
shadow data structure needs the
On Friday, 15 April 2016 at 18:33:44 UTC, Johan Engelen wrote:
Hi all,
When building a unittest case in Weka.io's codebase, I
measure that appendToModuleMember takes about 10% of the total
compile time, and about 25% of total semantic analysis time.
"appendToModuleMember" is the only
Hi all,
When building a unittest case in Weka.io's codebase, I measure
that appendToModuleMember takes about 10% of the total compile
time, and about 25% of total semantic analysis time.
"appendToModuleMember" is the only function that pops up in
profiling with such a large time fraction
20 matches
Mail list logo
