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).
— Dav
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 conv
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 s
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
https://github.com/dlan
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. Th
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 way
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 pre
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 ele
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 any
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 positive
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 *tw
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 l
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 a
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 functio
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 spe
20 matches
Mail list logo