OrderedDict Key Not Found #394

RobertRosca · 2018-07-08T21:42:12Z

I'm 90% sure this is something I've screwed up, but for some reason I get a key not found error for ordered dictionaries. My types are quite long and full of data, but I'm effectively making a Dict with integer keys, then sorting it.

For example, I have:

DataStructures.OrderedDict{Int64,JAXTAM.GTIData} with 320 entries:
  3   => JAXTAM.GTIData(:nustar, :FPMA, "10002008001", 1.0, 3, 3, [8, 7, 10, 6, 11, 14, 15, 13, 9, 8  …  6, 6, 9, 10…
  4   => JAXTAM.GTIData(:nustar, :FPMA, "10002008001", 1.0, 4, 42, [8, 10, 17, 12, 21, 13, 19, 8, 14, 16  …  14, 10,…
  5   => JAXTAM.GTIData(:nustar, :FPMA, "10002008001", 1.0, 5, 150, [6, 10, 14, 2, 16, 14, 8, 13, 19, 14  …  8, 10, …
  7   => JAXTAM.GTIData(:nustar, :FPMA, "10002008001", 1.0, 7, 389, [12, 16, 15, 13, 8, 15, 20, 6, 10, 11  …  11, 9,…
⋮

Where 3, 4, 5, 7, etc... are the integer keys:

Base.KeyIterator for a DataStructures.OrderedDict{Int64,JAXTAM.GTIData} with 320 entries. Keys:
  3
  4
  5
  7
⋮

But for some reason, if I try and access the key by doing gtis[3] (with gtis as the dict), I get a key not found error. More confusingly, in some (seemingly random) cases it does work for a couple of the keys.

Have I misunderstood something? This problem only happens if I use ordered dicts, I looked through the docs but couldn't figure anything out.

The text was updated successfully, but these errors were encountered:

timholy · 2018-07-09T01:32:15Z

We'd need a convenient way of reproducing this problem in order to debug it. OrderedDict has recently moved to OrderedCollections and will eventually be used to replace the implementation here. If you're using julia 0.7, it might be best to move this over there. (If not, better keep it here.)

RobertRosca · 2018-07-09T02:18:40Z

I'm currently on 0.6. I'll see if I can reproduce this in a simpler way than setting up the package I'm working on. Here's an asciinema recording of the issue, if it helps clarify things at all (excuse the slowness, I'm not precompiling my package yet).

The testing I've done so far didn't really clarify anything, it just made me more confused if anything:

              _
   _       _ _(_)_     |  A fresh approach to technical computing
  (_)     | (_) (_)    |  Documentation: https://docs.julialang.org
   _ _   _| |_  __ _   |  Type "?help" for help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 0.6.3 (2018-05-28 20:20 UTC)
 _/ |\__'_|_|_|\__'_|  |  Official http://julialang.org/ release
|__/                   |  x86_64-pc-linux-gnu

julia> using JAXTAM

julia> lc = JAXTAM.lcurve(:nustar, "80002013010", 1);
INFO: Loading /media/robert/8C08EB2F08EB16CC/Users/Robert/heasarc/nustar/master.jld2
INFO: Loading /media/robert/8C08EB2F08EB16CC/Users/Robert/heasarc/nustar/append.jld2
INFO: Loading LC 80002013010: from /media/robert/8C08EB2F08EB16CC/Users/Robert/heasarc/nustar/nustar/nustar_archive/80002013010/JAXTAM/lc/1/

julia> gtis = JAXTAM._gtis(lc[:FPMA])
INFO: Original counts: 313690, counts in GTI: 299092, delta: -14598 (-4.65 %)
WARNING: Excluded 168 gtis (< 5s) out of 192
Dict{Int64,JAXTAM.GTIData} with 24 entries:
  32  => JAXTAM.GTIData(:nustar, :FPMA, "80002013010", 1.0, 32, 29097, [5, 6, 10, 7, 9, 7, 6, 10, 8, 10  …  11, 12, 10, 8, 6, 14, 7, 6, 7, …
  50  => JAXTAM.GTIData(:nustar, :FPMA, "80002013010", 1.0, 50, 58259, [12, 8, 7, 6, 13, 6, 7, 6, 7, 7  …  9, 14, 11, 5, 9, 6, 7, 10, 8, 0]…
  40  => JAXTAM.GTIData(:nustar, :FPMA, "80002013010", 1.0, 40, 53738, [7, 7, 7, 3, 12, 8, 6, 5, 3, 4  …  6, 5, 11, 5, 7, 5, 6, 9, 11, 3], …
............................................................ (removed for this comment)

julia> gtis_sorted = sort(gtis)
DataStructures.OrderedDict{Int64,JAXTAM.GTIData} with 24 entries:
  1   => JAXTAM.GTIData(:nustar, :FPMA, "80002013010", 1.0, 1, 1, [8, 8, 10, 6, 2, 5, 5, 4, 12, 8  …  6, 7, 7, 6, 6, 6, 11, 7, 8, 0], [0.0,…
  4   => JAXTAM.GTIData(:nustar, :FPMA, "80002013010", 1.0, 4, 41, [5, 9, 6, 10, 11, 3, 9, 9, 6, 8  …  15, 8, 6, 12, 10, 6, 11, 6, 7, 3], […
  7   => JAXTAM.GTIData(:nustar, :FPMA, "80002013010", 1.0, 7, 2766, [4, 5, 6, 3, 5, 10, 8, 12, 4, 10  …  9, 6, 6, 9, 7, 7, 7, 8, 4, 6], [0…
  10  => JAXTAM.GTIData(:nustar, :FPMA, "80002013010", 1.0, 10, 2808, [14, 6, 4, 8, 6, 7, 5, 10, 11, 7  …  12, 16, 6, 8, 1, 7, 5, 10, 5, 1]…
  21  => JAXTAM.GTIData(:nustar, :FPMA, "80002013010", 1.0, 21, 5817, [2, 11, 13, 8, 10, 8, 11, 9, 7, 8  …  12, 8, 8, 6, 7, 5, 5, 14, 6, 1]…
............................................................ (removed for this comment)

julia> gtis_sorted[1]
ERROR: KeyError: key 1 not found
Stacktrace:
 [1] getindex(::DataStructures.OrderedDict{Int64,JAXTAM.GTIData}, ::Int64) at /home/robert/.julia/v0.6/DataStructures/src/ordered_dict.jl:361

julia> gtis_sorted[2]
ERROR: KeyError: key 2 not found
Stacktrace:
 [1] getindex(::DataStructures.OrderedDict{Int64,JAXTAM.GTIData}, ::Int64) at /home/robert/.julia/v0.6/DataStructures/src/ordered_dict.jl:361

julia> gtis_sorted[10]
ERROR: KeyError: key 10 not found
Stacktrace:
 [1] getindex(::DataStructures.OrderedDict{Int64,JAXTAM.GTIData}, ::Int64) at /home/robert/.julia/v0.6/DataStructures/src/ordered_dict.jl:361

julia> k = keys(gtis_sorted)
Base.KeyIterator for a DataStructures.OrderedDict{Int64,JAXTAM.GTIData} with 24 entries. Keys:
  1
  4
  7
  10
  21
  23
  25
  27
  29
  32
  33
  36
  37
  38
  39
  40
  46
  48
  50
  53
  56
  125
  126
  127

julia> for k in k
           try
               println(gtis_sorted[k].gti_index) # git_index is the same as the key value
           catch
               warn(k)
           end
       end
WARNING: 1
WARNING: 4
WARNING: 7
WARNING: 10
WARNING: 21
23
WARNING: 25
WARNING: 27
WARNING: 29
WARNING: 32
WARNING: 33
WARNING: 36
37
WARNING: 38
WARNING: 39
WARNING: 40
46
WARNING: 48
WARNING: 50
WARNING: 53
WARNING: 56
WARNING: 125
WARNING: 126
WARNING: 127

timholy · 2018-07-09T08:57:17Z

Thanks. For the record, while the asciicinema recording was cool, to save you time in the future that's not necessary. Since JAXTAM isn't a registered package, a link to the repository (I found it) and the steps to reproduce it were all that was needed.

But currently I don't think I can help, I get:

julia> lc = JAXTAM.lcurve(:nustar, "80002013010", 1);
ERROR: KeyError: key :nustar not found
Stacktrace:
 [1] getindex(::Dict{Any,Any}, ::Symbol) at ./dict.jl:474
 [2] master(::Symbol) at /tmp/pkgs/v0.6/JAXTAM/src/io/master_tables.jl:112
 [3] master_a at /tmp/pkgs/v0.6/JAXTAM/src/io/master_append.jl:124 [inlined]
 [4] master_query at /tmp/pkgs/v0.6/JAXTAM/src/io/master_tables.jl:183 [inlined]
 [5] #lcurve#46 at /tmp/pkgs/v0.6/JAXTAM/src/science/lcurve.jl:149 [inlined]
 [6] lcurve(::Symbol, ::String, ::Int64) at /tmp/pkgs/v0.6/JAXTAM/src/science/lcurve.jl:149

When I try Pkg.build("JAXTAM") (which is not done automatically for un-registered packages, might help to mention it in your README) I get

INFO: Building JAXTAM                                                                                                                                                                        
Installing dependency lftp via `sudo apt-get install lftp`:                                                                                                                                  
[sudo] password for tim:                                                                                                                                                                     
Reading package lists... Done                                                                                                                                                                
Building dependency tree       
Reading state information... Done
lftp is already the newest version (4.8.1-1).
0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
======================================================================================[ ERROR: JAXTAM ]======================================================================================

LoadError: Provider BinDeps.PackageManager failed to satisfy dependency lftp
while loading /tmp/pkgs/v0.6/JAXTAM/deps/build.jl, in expression starting on line 65

=============================================================================================================================================================================================

======================================================================================[ BUILD ERRORS ]=======================================================================================

WARNING: JAXTAM had build errors.

 - packages with build errors remain installed in /tmp/pkgs/v0.6
 - build the package(s) and all dependencies with `Pkg.build("JAXTAM")`
 - build a single package by running its `deps/build.jl` script

=============================================================================================================================================================================================

This was on Kubuntu 18.04. I've manually installed libhdf5, however, and I still get that :nustar key error.

I don't have time to figure this out further, sorry.

oxinabox · 2018-07-09T09:18:50Z

Here is a Minimum Failing Example
without any 3rd party packages.

julia> idict = Dict(k=>string(k) for k in 1:10)
Dict{Int64,String} with 10 entries:
  7  => "7"
  4  => "4"
  9  => "9"
  10 => "10"
  2  => "2"
  3  => "3"
  5  => "5"
  8  => "8"
  6  => "6"
  1  => "1"

julia> sdict = sort(idict)
DataStructures.OrderedDict{Int64,String} with 10 entries:
  1  => "1"
  2  => "2"
  3  => "3"
  4  => "4"
  5  => "5"
  6  => "6"
  7  => "7"
  8  => "8"
  9  => "9"
  10 => "10"

julia> sdict[1]
ERROR: KeyError: key 1 not found
Stacktrace:
 [1] getindex(::DataStructures.OrderedDict{Int64,String}, ::Int64) at /home/lyndon/.julia/v0.6/DataStructures/src/ordered_dict.jl:361

julia> sdict[2]
ERROR: KeyError: key 2 not found
Stacktrace:
 [1] getindex(::DataStructures.OrderedDict{Int64,String}, ::Int64) at /home/lyndon/.julia/v0.6/DataStructures/src/ordered_dict.jl:361

julia> versioninfo()
Julia Version 0.6.3
Commit d55cadc350 (2018-05-28 20:20 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Core(TM) i7-3820 CPU @ 3.60GHz
  WORD_SIZE: 64
  BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Sandybridge)
  LAPACK: libopenblas64_
  LIBM: libopenlibm
  LLVM: libLLVM-3.9.1 (ORCJIT, sandybridge)

julia> Pkg.installed("DataStructures")
v"0.8.3"

oxinabox · 2018-07-09T09:35:16Z

Even more minimal case:
sort(Dict(k=>string(k) for k in 1:3))[1]

It seems not to occur for keys of 1:1 or 1:2, but 1:3 does it

I don't really follow how OrderedDict (or hash tables) work closely,
But I suspect this is due to ht_keyindex and ht_keyindex2 disagreeing.
I feel like for things that are contained inside the ordered dict they should agree.
and ht_keyindex2 is used to construct OrderedDicts , and ht_keyindex is used to sort them.
Since constructing works fine,
but sorting is broken,
I thus theorize that ht_keyindex is borked.

julia> odict = OrderedDict(Dict(k=>string(k) for k in 1:3))
DataStructures.OrderedDict{Int64,String} with 3 entries:
  2 => "2"
  3 => "3"
  1 => "1"

julia> DataStructures.ht_keyindex2.(odict,1:3)
3-element Array{Int64,1}:
 3
 1
 2

julia> DataStructures.ht_keyindex.(odict, 1:3, false)
3-element Array{Int64,1}:
 16
  6
  7

julia> odict[1]
"1"

julia> odict[2]
"2"

julia> odict[3]
"3"

julia> sort(odict)[1]
ERROR: KeyError: key 1 not found
Stacktrace:
 [1] getindex(::DataStructures.OrderedDict{Int64,String}, ::Int64) at /home/lyndon/.julia/v0.6/DataStructures/src/ordered_dict.jl:361

oxinabox · 2018-07-09T09:47:16Z

My suspicion is confirmed.
By changing

DataStructures.jl/src/dict_sorting.jl

Line 16 in 437f0bf

idx = ht_keyindex(d, key, false)

to

 idx = ht_keyindex2(d, key)

This issue goes away.

Actually on further investigation I think that ht_keyindex and ht_keyindex2 are fine.
But I don't think in sort the way slots is being mutated while ht_keyindex is being read is safe.

Fix #394 with the missing keys after sorting

NRHelmi · 2021-02-22T14:49:10Z

Hi everyone, I see that the issue is closed but I'm facing it again using julia 1.5.4.

julia> dict_result[253282] # works

julia> sort(dict_result)[253282]
ERROR: KeyError: key 253282 not found
Stacktrace:
 [1] getindex(::OrderedCollections.OrderedDict{Int64,Array}, ::Int64) at /root/.julia/packages/OrderedCollections/DqfZ7/src/ordered_dict.jl:346
 [2] top-level scope at REPL[23]:1

I don't really have a reproducible example 😅 , just want to mention that it happens again and only for that specific index my side.
Thanks

kmsquire · 2021-02-22T15:11:53Z

@NRHelmi can you check which version of OrderedCollections you have installed? A variant of this bug was fixed in a recent release of that package (which is pulled in and re-exported by DataStructures.jl).

NRHelmi · 2021-02-22T15:18:31Z

@kmsquire I believe the OrderedCollections version I'm using is 1.3.2.

oxinabox added a commit that referenced this issue Jul 9, 2018

=Fix #394

4cc80fb

oxinabox mentioned this issue Jul 9, 2018

Fix #394 with the missing keys after sorting #395

Merged

timholy closed this as completed in ebffdd1 Jul 9, 2018

timholy added a commit that referenced this issue Jul 9, 2018

Merge pull request #395 from JuliaCollections/ox/394

431e99d

Fix #394 with the missing keys after sorting

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

OrderedDict Key Not Found #394

OrderedDict Key Not Found #394

RobertRosca commented Jul 8, 2018 •

edited

Loading

timholy commented Jul 9, 2018

RobertRosca commented Jul 9, 2018

timholy commented Jul 9, 2018 •

edited

Loading

oxinabox commented Jul 9, 2018 •

edited

Loading

oxinabox commented Jul 9, 2018 •

edited

Loading

oxinabox commented Jul 9, 2018 •

edited

Loading

NRHelmi commented Feb 22, 2021

kmsquire commented Feb 22, 2021

NRHelmi commented Feb 22, 2021

OrderedDict Key Not Found #394

OrderedDict Key Not Found #394

Comments

RobertRosca commented Jul 8, 2018 • edited Loading

timholy commented Jul 9, 2018

RobertRosca commented Jul 9, 2018

timholy commented Jul 9, 2018 • edited Loading

oxinabox commented Jul 9, 2018 • edited Loading

oxinabox commented Jul 9, 2018 • edited Loading

oxinabox commented Jul 9, 2018 • edited Loading

NRHelmi commented Feb 22, 2021

kmsquire commented Feb 22, 2021

NRHelmi commented Feb 22, 2021

RobertRosca commented Jul 8, 2018 •

edited

Loading

timholy commented Jul 9, 2018 •

edited

Loading

oxinabox commented Jul 9, 2018 •

edited

Loading

oxinabox commented Jul 9, 2018 •

edited

Loading

oxinabox commented Jul 9, 2018 •

edited

Loading