bugGNU Octave - Bugs: bug #49559, Implementation of containers.Map

 
 

bug #49559: Implementation of containers.Map

Submitter:  Guillaume <gyom>
Submitted:  Tue 08 Nov 2016 02:26:43 PM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Feature Request
Status:  Fixed Assigned to:  siko1056
Originator Name:  Guillaume Open/Closed:  * Closed
Release:  * dev Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Fri 07 Apr 2017 07:30:41 PM UTC, comment #22: 

Okay, final changeset is here http://hg.savannah.gnu.org/hgweb/octave/rev/b04466113212.

This sets the ValueType to "any" whenever the values are not scalars, not just when they differ in size.

It also improves the performance ever so slightly by replacing a test on isfield() followed by code when the test is succesful, to a try/catch block.

Finally, non-existent keys which generate an error message are now pretty-printed.

I'm going to close this report now.  Any further incompatibilities can get their own bug report.

Rik <rik5>
Group administrator
Fri 07 Apr 2017 05:26:21 PM UTC, comment #21: 


>> version
ans = 9.1.0.441655 (R2016b)

>> m = containers.Map ([1, 2], {magic(3), eye(3)})
m = Map with properties:

        Count: 2
      KeyType: double
    ValueType: any

>> m.ValueType

ans = any


A.R. Burgers <arb>
Fri 07 Apr 2017 04:46:55 PM UTC, comment #20: 

I don't think it makes sense to keep a copy of the keys internally.  They are already stored once as the fieldnames of the internal struct used for the implementation.  And we use a struct for implementation, rather than just a cell array of keys and a cell array of values, because the search time for a key would be linear in a cell array, but is O(log2 (N)) for a struct which maps internally to a C++ map.  At some point we could consider a true O(1) containers.Map, but this would require mapping onto C++'s <unordered_map>.

It would be nice if we had a code coverage tool for m-files.  I found that the BIST tests for Map were not exercising every line of the code.  In particular, moving back to num2hex/hex2num had broken the values() function when using the two-argument form of the function to extract particular keys.

I added yet more BIST tests, fixed values(), added support for horzcat, changed check_types to check ValueType against the full list of allowed types, and changed the calculation for allowed sizes.  The last bit needs checking.

In Matlab, could someone try


m = containers.Map ([1, 2], {magic(3), eye(3)})
m.ValueType


In Octave, this returns "double" because the objects are of the same type and same size.  However, Matlab may have intended for this to be same type and scalar.

The cset is here http://hg.savannah.gnu.org/hgweb/octave/rev/56c59b3f9172.



Rik <rik5>
Group administrator
Thu 06 Apr 2017 07:13:26 PM UTC, comment #19: 

Guillaume: I pushed your changes and added another that uses some new features for num2hex and hex2num.  Those functions can now work on integer types as well as handle cell arrays.

  http://hg.savannah.gnu.org/hgweb/octave/rev/42bd10feedfa

I'm not sure what the intent is, but would it make sense to always keep the keys stored in a cell array, at least internally?  If so, there may be some calls to cell2X or X2cell functions that could be eliminated.

John W. Eaton <jwe>
Group administrator
Thu 06 Apr 2017 12:45:03 PM UTC, comment #18: 

Thank you both for your inputs - it's very informative to look at the changes you've made. And the speed improvements are great.

I attach a small patch to set ValueType to "any" if the values are not scalar. It also makes sure keys and values are row vectors as this property was lost with some of the changes. I also modified the "sort_keys" function to decode numeric keys before sorting as mentioned by Rik - I didn't want to do that earlier for performance reasons but it seems to be less of an issue now. Otherwise have a look at the end of comment #14 for a way to sort numeric keys with negative values correctly (ie take the negative of positive values and the 2-complement of negative values before calling sort).

Thank you.

(file #40291)

Guillaume <gyom>
Wed 05 Apr 2017 11:10:08 PM UTC, comment #17: 

@jwe: Your code does correctly handle intmax, however Map is now back to failing to sort numeric keys with negative values correctly.


m = containers.Map('KeyType','double','ValueType','char');
m(-2)='a';
m(-1)='b';
m(0)='c';
m(1)='d';
m(2)='e';
keys (m)
ans =
{
  [1,1] = 0
  [2,1] =  1
  [3,1] =  2
  [4,1] = -1
  [5,1] = -2
}


You could save the signbit separately at the front of the string that is produced.  Or you could decode numeric keys back from strings to numbers, sort them, and pass the sorted list to orderfields rather than relying on the default.  There's probably some other strategies that work.

Rik <rik5>
Group administrator
Wed 05 Apr 2017 09:17:19 PM UTC, comment #16: 

Rik: typecast should also handle negative values since it is just a reinterpretation of the bits of the input value.  My idea was that you could exactly convert any value to 16 hex characters.  Using sprintf with a %g format causes trouble for large 64-bit integer values.  See for example this test:


key = intmax ("uint64");
m = containers.Map (key, pi);
assert (m.keys (), {key})


I checked in the following changeset.  I think the performance is still good, at least it is with this test:


n = 2e3; tic; mapObj = containers.Map(num2cell(1:n),1:n); toc


http://hg.savannah.gnu.org/hgweb/octave/rev/95744d6d7d3b

John W. Eaton <jwe>
Group administrator
Wed 05 Apr 2017 06:13:20 PM UTC, comment #15: 

@Guillaume: Thank you for the excellent work.  I made some changes for performance, and to fix the issue with ordering of numeric keys, and checked it in here (http://hg.savannah.gnu.org/hgweb/octave/rev/5ab7192f91d8).  Any further development can take place on the development branch.

Using the example with 2,000 key pairs, the original code ran in an average of 143 milliseconds.

One of the first things I did was to optimize the use of cellfun.  Unfortunately, arbitrary anonymous functions as inputs to cellfun are slower than using the small list of know functions which are accelerated in cellfun.  Instead of writing,


all (cellfun (@(x) isreal (x) && isscalar (x), keys))


I wrote


all (cellfun ("isreal", keys) & (cellfun ("numel", keys) == 1))


Changes of this sort made a -25% difference in run time to 107 milliseconds.

Next, I agree that the keys should always be strings, but rather than use typecast and num2hex I simply use sprintf.


keys = ostrsplit (sprintf ("%.16g\n", keys{:}), "\n");


This brings the runtime down to ~40 milliseconds or -70% of the original code.  It has the added benefit of properly handling numeric keys with negative values.

I also added extensive BIST testing for the error conditions.

There is still some more work to do.  Matlab documentation suggests that different sizes should cause the ValueType to be set to "any".


Default: 'any' when you create an empty Map object or when you specify values of different sizes or types, otherwise determined by the data type of valueSet.


Currently, Octave makes the decision based on multiple value type, but not their sizes.  Could someone with access to Matlab try the following?


m = containers.Map ([1, 2], {magic(3), magic(4)})
m.ValueType


Octave returns "double".

As a second issue, do we need to follow Matlab exactly and not implement horzcat?  Octave is a superset of Matlab and if a programmer writes


map3 = [map1, map2]


it seems pretty obvious that they meant to concatenate the two.




Rik <rik5>
Group administrator
Wed 29 Mar 2017 03:02:29 PM UTC, comment #14: 

Many thanks for the review, Kai.

I attach a new version fixing a), b), and d). For the performance issue c), it seems that most of the time is spent in ordering the keys (a call of orderfields()). I replaced it with a call to sort() before encoding the keys:


>> n = 2e3; t1=tic; mapObj = containers.Map(num2cell(1:n),1:n); toc(t1), t2=tic; mapObj(n-5), toc(t2)
Elapsed time is 0.196254 seconds.
ans =  1995
Elapsed time is 0.00353098 seconds.


This makes me notice that orderfields() is slow because of the loop at the end of this function; there might be a faster way to implement it by using cell2struct(). I also tried to use sortrows() but came across bug #42523; contrary to the comments there, I think the issue is not with sort() itself but that sortrows() should call cell2mat() before sort() if the input is a cell.

Now, with current implementation, keys will be automatically sorted appropriately (and relatively quickly) when using the constructor. Ordering using orderfields() will still be called when a new key/value pair is added to the map, and this will be slow for large maps:


n = 2e3;
tic; mapObj = containers.Map(num2cell(1:n),1:n); toc
Elapsed time is 0.195531 seconds.
tic; mapObj(n+1) = 0; toc
Elapsed time is 3.00148 seconds.


Hopefully this can be fixed by improving orderfields().

Finally, I looked at how to fix the ordering of keys when they are numeric and contain negative values. Currently:


>> m = containers.Map([-2 -1 0 1 2],{'a','b','c','d','e'});
>> keys(m) ## keys have been sorted according to [-2 -1 0 1 2]
ans =
{
  [1,1] = -2
  [1,2] = -1
  [1,3] = 0
  [1,4] =  1
  [1,5] =  2
}
>> m = containers.Map('KeyType','double','ValueType','char');
>> m(-2)='a';
>> m(-1)='b';
>> m(0)='c';
>> m(1)='d';
>> m(2)='e';
>> keys(m) ## keys have been sorted according to num2hex'ed [-2 -1 0 1 2]
ans =
{
  [1,1] = 0
  [1,2] =  1
  [1,3] =  2
  [1,4] = -1
  [1,5] = -2
}


It seems that using something along the lines of the following would work (taking the negative of positive values, and the complement of negative values):


X = [-2 -1 0 1 2];
hex2num(sort(cellstr(num2hex(X))))

i = X >= 0; j = X < 0;
X = typecast(X,'int64');
X(i) = bitset(X(i),64,1);
X(j) = bitcmp(X(j),'int64');
X = typecast(X,'double');

K = sort(cellstr(num2hex(X)))

Y = hex2num(K);
i = Y <= 0; j = Y > 0;
Y = typecast(Y,'int64');
Y(i) = bitset(Y(i),64,0);
Y(j) = bitcmp(Y(j),'int64');
Y = typecast(Y,'double')


The code above works in Matlab but not Octave as there seems to be compatibility issues with bitset().

(file #40196)

Guillaume <gyom>
Wed 29 Mar 2017 12:07:27 PM UTC, comment #13: 

Here my first review mostly trying all of MATLAB's documentation https://www.mathworks.com/help/matlab/map-containers.html. I really can hardly make up, whether I am using MATLAB's implementation or yours. Very impressive! Only a few small things to make it perfectly indistinguishable:

a) I think Map.subsref, the cases "isKey" and "remove" are missing?


>> mapObj = containers.Map ({'a','b','c'}, {1,2,3});
>> mapObj.isKey('a')

error: The name 'isKey' is not an accessible property for an instance of class 'containers.Map'.
error: called from
    subsref at line 331 column 15
>> isKey (mapObj, 'a')

ans = 1
>> mapObj.remove('a')

error: The name 'remove' is not an accessible property for an instance of class 'containers.Map'.
error: called from
    subsref at line 331 column 15
>> remove (mapObj, 'a')

containers.Map object with properties:

   Count     : 2
   KeyType   : char
   ValueType : double


b) There is a forgotten semicolon for the case "values" in Map.subsref.

c) Another one is performance:


Matlab R2017a:

>> n = 2e5; t1=tic; mapObj = containers.Map(num2cell(1:n),1:n); toc(t1), t2=tic; mapObj(n-5), toc(t2)
Elapsed time is 0.155456 seconds.
ans =
      199995
Elapsed time is 0.000330 seconds.

Yours:

>> n = 2e3; t1=tic; mapObj = containers.Map(num2cell(1:n),1:n); toc(t1), t2=tic; mapObj(n-5), toc(t2)
Elapsed time is 3.55376 seconds.
ans =    1.99500000000000e+03
Elapsed time is 0.00406289 seconds.


So it hardly works with 1e4 key-values. But I think this is acceptable.

d) Regarding the documentation, we have the convention to write two spaces after a period, see http://wiki.octave.org/Help_text#Whitespace .


Some words.  Another words.


That's all. I am perfectly fine with it.

Kai Torben Ohlhus <siko1056>
Group Member
Tue 28 Mar 2017 04:52:58 PM UTC, comment #12: 

I won't have time until the weekend, but I'll try and give a second review to Kai's main review.

Rik <rik5>
Group administrator
Tue 28 Mar 2017 09:01:32 AM UTC, comment #11: 

Thanks, Kai. Not sure where it should go, maybe in "scripts/general"?

It will be useful to hear from Rik as it is something he looked at as well. In particular, a decision should be made on whether or not to sort keys (and how).

Guillaume <gyom>
Mon 27 Mar 2017 09:16:09 PM UTC, comment #10: 

Thank you for your effort. Do you have another idea about the location of file #40168, or should I deploy it in "scripts/+containers/Map.m"? I review your file tomorrow, when I can check with Matlab.

Kai Torben Ohlhus <siko1056>
Group Member
Mon 27 Mar 2017 11:47:38 AM UTC, comment #9: 

I am attaching a new version of a possible implementation of containers.Map with many changes:

  • more documentation,
  • more tests,
  • improved validation of inputs for better compatibility with Matlab,
  • use of a struct instead of a cell vector to store key/value pairs. Numeric arrays are converted to strings using typecast/num2hex, using a suggestion from jwe.


It requires reviewing and some code refactoring might be possible for the validation of user-provided keys or values.

According to the documentation, keys are not sorted but in practice they are. This implementation does the same. There is still however an issue with negative numbers (sort takes place on num2hex'ed keys) so unless there is a better solution, a way to fix this is modify private methods encode_keys/decode_keys to implement the approach described here:
http://brownbag.springmetrics.com/2012/05/making-numbers-sortable/

(file #40168)

Guillaume <gyom>
Fri 03 Feb 2017 04:16:06 PM UTC, comment #8: 

Ok, thanks. I'll stop looking at it then. Here are some tests you might find useful.


%!test
%! m = containers.Map ();
%! assert (m.Count, uint64 (0));
%! assert (isempty (m));
%! assert (isempty (keys (m)));
%! assert (isempty (values (m)));
%! assert (isKey (m, "Octave"), false);
%! assert (isKey (m, 42), false);

%!test
%! key = {"One", "Two", "Three", "Four"};
%! val = [1, 2, 3, 4];
%! m = containers.Map (key, val);
%! assert (m.Count, uint64 (4));
%! assert (m("Two"), 2);
%! m("Five") = 5;
%! key2 = {"Six", "Seven", "Eight"};
%! val2 = [6, 7, 8];
%! m2 = containers.Map (key2, val2);
%! m = [m; m2];
%! assert (m.Count, uint64 (8));
%! k = keys (m);
%! assert (isempty (setdiff (k, [key, "Five", key2])));
%! v = values (m, {"Three", "Four", "Five"});
%! assert (v, {3, 4, 5});
%! remove (m, {"Three", "Four"});
%! k = keys (m);
%! assert (numel (k), 6);

%!test
%! key = [2, 3, 4];
%! val = {eye(2), eye(3), eye(4)};
%! m = containers.Map (key, val);
%! assert (m(3), eye(3));

%!test
%! m = containers.Map ("KeyType","char", "ValueType","int32");
%! assert (m.KeyType, "char");
%! assert (m.ValueType, "int32");

%!test
%! key = {"one", "two", "three"};
%! val = {1, 2, 3};
%! m = containers.Map (key, val, "UniformValues",false);
%! m("four") = "GNU";
%! assert (values (m), {"GNU", 1, 3, 2});


Guillaume <gyom>
Fri 03 Feb 2017 03:28:19 PM UTC, comment #7: 

I made a lot of progress towards using octave structs to efficiently implement containers.Map.  Hopefully this weekend I will either be able to commit the changes, or upload them to this bug report for further review.

Rik <rik5>
Group administrator
Fri 03 Feb 2017 02:38:27 PM UTC, comment #6: 

Just adding as a reminder that containers.Map, keys, values, isKey and remove will have to be removed from the list of missing functions in scripts/help/__unimplemented__.m

Guillaume <gyom>
Thu 02 Feb 2017 05:37:07 PM UTC, comment #5: 

Rik, I was looking at modifying the current implementation following your suggestion to convert numeric keys to strings. How would you implement the keys() method, ie recover what the keys were before being converted to strings? Use sscanf() or str2num()?
Also, in Matlab, keys are also sorted and this would have to happen when the keys are numeric - as a consequence there might be a lot of conversions back and forth when entries are added or removed or when the keys(), values() methods are called.

Guillaume <gyom>
Fri 02 Dec 2016 05:00:14 PM UTC, comment #4: 

Okay.  I'll try to look at this on the weekend.  I think I can get by using a struct everywhere by converting numeric keys to strings with


sprintf ("%.16g", key)


For something short, like 2.1, the string will be "2.1".  For something like pi, the string would be "3.141592653589793".  Since IEEE double only carries 16 digits of precision the keys will be unique even if I don't store them in numeric format.  And it makes the underlying implementation easier since I can use the same code for both cases.

Rik <rik5>
Group administrator
Fri 02 Dec 2016 11:25:55 AM UTC, comment #3: 

Thanks for looking into this. I started the implementation using cell arrays to store keys with the thought that the keys could be anything, or at least a mix between char and numeric. But given that they can only be either char vectors or scalars, it makes sense to use structs for char vector keys (esp. as Octave allows any string as fieldname) and a numeric array for scalar keys.

So the change is going from


keySet   = {...}
valueSet = {...}


to


map = struct(keys, vals)


for KeyType "char" or the following for other KeyTypes:


keySet   = [...]
valueSet = {...}


Rik, if you have the time to go into this, please do so. This will be quite a bit of change to what I wrote but a significant part of the code is also to deal with the various inputs and methods.

Guillaume <gyom>
Thu 01 Dec 2016 06:41:22 PM UTC, comment #2: 

I took a look at your implementation.  I do think we need to have a map/hash structure available in Octave.  However, I think it should be based on structs which internally use std::set and are quite fast.  I did some benchmarking which shows that a struct implementation would be 500X faster.


vals = num2cell ([1:100]');
keys = cellfun (@(x) sprintf ("%d", x), vals, "unif", false);

map = Map (keys, vals)
containers.Map object with properties:

   Count     : 100
   KeyType   : char
   ValueType : double

tic; map("50"); toc
Elapsed time is 0.0261769 seconds.

for i = 1:100
> smap.(keys{i}) = vals{i};
> endfor

tic; smap.("50"); toc
Elapsed time is 5.19753e-05 seconds.

.026 / 5e-5
ans =  520


Would you be interested in making the necessary changes?  I seem to recall that we still haven't sorted out a copyright assignment for you due to concerns over remaining anonymous.  If you want, I can take over from here and modify the code and use my name on the copyright.  Or we can work with Mike Miller or someone at the FSF to figure out the licensing situation.


Rik <rik5>
Group administrator
Wed 09 Nov 2016 11:29:59 AM UTC, comment #1: 

I've added concatenation and refined input checking, see attachment. Feedbacks welcome.

(file #38912)

Guillaume <gyom>
Tue 08 Nov 2016 02:26:43 PM UTC, original submission:  

Hash tables are available in Matlab with the containers.Map class:

https://www.mathworks.com/help/matlab/map-containers.html

I wrote an Octave implementation that should have the same functionalities even if it will be much slower for large tables as it doesn't formally implement an hashmap (I guess we should use a wrapper to java or C++ for that instead). The class file is attached here (to be copied in a +containers folder). if you think this might anyway be useful, I can add some help text and unit tests.

Guillaume <gyom>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #40291:  fixmap.diff added by gyom (3KiB - text/x-patch)
file #40196:  Map.m added by gyom (19KiB - d2l/unknowntype)
file #40168:  Map.m added by gyom (18KiB - d2l/unknowntype)
file #38912:  Map.m added by gyom (8KiB - text/x-objective-c)
file #38905:  Map.m added by gyom (7KiB - text/x-objective-c)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by arb (Posted a comment)
  • -email is unavailable- added by jwe (Posted a comment)
  • -email is unavailable- added by siko1056 (Posted a comment)
  • -email is unavailable- added by siko1056 (Interested)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by gyom (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 11 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2017-04-07 rik5 StatusIn Progress Fixed
        Open/ClosedOpen Closed
    2017-04-06 gyom Attached File- Added fixmap.diff, #40291
    2017-03-29 gyom Attached File- Added Map.m, #40196
    2017-03-27 siko1056 Assigned toNone siko1056
    2017-03-27 gyom Attached File- Added Map.m, #40168
    2017-03-20 siko1056 Carbon-Copy- Added siko1056
    2016-12-02 rik5 StatusPatch Submitted In Progress
    2016-12-01 rik5 StatusNone Patch Submitted
    2016-11-09 gyom Attached File- Added Map.m, #38912
    2016-11-08 gyom Attached File- Added Map.m, #38905

    Back to the top

    Powered by Savane 3.13-4448.
    Corresponding source code