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

 
 

bug #49559: Implementation of containers.Map

Submitted by:  Guillaume <gyom>
Submitted on:  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:  Kai Torben Ohlhus <siko1056>
Originator Name:  Guillaume Open/Closed:  Closed
Release:  dev Operating System:  Any

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

( 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>
Project Administrator
Fri 07 Apr 2017 05:26:21 PM UTC, comment #21:
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

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>
Project 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>
Project 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.

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>
Project 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:

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

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

John W. Eaton <jwe>
Project 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,

I wrote

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.

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".

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

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

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

Rik <rik5>
Project 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:

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:

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:

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):

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?

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

c) Another one is performance:

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 .

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

Kai Torben Ohlhus <siko1056>
Project MemberIn charge of this item.
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>
Project 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>
Project MemberIn charge of this item.
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.

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>
Project 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

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>
Project 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

to

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

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.

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>
Project 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)
  •  

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only project 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.4