bugGNU Octave - Bugs: bug #52756, implement xor as C++ function

 
 

bug #52756: implement xor as C++ function

Submitter:  Rik <rik5>
Submitted:  Thu 28 Dec 2017 09:49:57 PM UTC
   
 
Category:  Octave Function Severity:  1 - Wish
Priority:  5 - Normal Item Group:  Performance
Status:  Confirmed Assigned to:  None
Originator Name:  Open/Closed:  * Open
Release:  * dev Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Tue 16 Jan 2018 05:59:39 PM UTC, comment #3: 

Ah! I forgot to write this, if the patch is correct and is ready to be pushed, kindly delete the xor.m file in ./scripts/general/ otherwise it would then show the warning of shadowing an in-built function.

Sahil <batterylow>
Tue 16 Jan 2018 05:47:03 PM UTC, comment #2: 

So i got to know that the function was to be implemented as a core function rather than an oct file and i gave it quite some time.

I have implemented it now in ./libinterp/corefcn/data.cc as an inbuilt function. Everything looks fine to me including the help text, usage, test cases etc.

Regarding the time taken :
The script that you provided runs in almost the same time now, i have had many applications running simultaneously so the time was elevated for both the functions (0.34 seconds for xor and 0.30 seconds for or). I think this is fine enough. Time complexity again has been O(n) (Couldn't think of less than that though).

I have basically implemented xor like this :


xor(a,b) = !a != !b


I had tried making a whole new operator for xor and tried mapping it to '^' operator of c++, but was unable to do so because of the problem that i had been treating (using the already written macros for operators) the operator^ as logical whereas of course it's bitwise (and ended up changing all the files related to operators in liboctave and libinterp, eventually, messing up the source and starting from scratch).

The only difference between the .m version and this is, the error that it throws is now the one in error.h and not the one that had been hard coded in xor.m . More precisely, we now get this (the following is the output of one of the assert test statements):


Expected <X and Y must be of compatible size or scalars>, but got <mx_el_ne: nonconformant arguments (op1 is 3x2, op2 is 2x3)>


Though I tried my best, there may be some styling mistakes, which will be rectified as soon as you point them out.

Kindly, do tell me if there's anything wrong in my approach. This task has really deepened my understanding of the octave codebase as well as mercurial.
Looking forward for a successful push of the changeset :-)

(file #42926)

Sahil <batterylow>
Fri 05 Jan 2018 09:42:15 PM UTC, comment #1: 

The code that i wrote took around 0.14 seconds against 0.09 seconds taken by the 'or' function on the script that you provided.

It fails the test cases when we need to use 'bsxfun', in that case i would request you to have a look at the code and suggest edits in the try{} block (because i think bsxfun is not correctly implemented using feval function). I have added two more test cases which are currently failing due to the same reason. Moreover, I didn't get why octave exits with signal 11 when it is failing those tests (it should instead throw the error).

All other test cases are passed successfully.Thanks.

Steps to reproduce:
1. Save the code in top level directory of the source, naming it xor1.cc
2. mkoctfile xor1.cc
3. test xor1


(file #42854)

Sahil <batterylow>
Thu 28 Dec 2017 09:49:57 PM UTC, original submission:  

The xor function, as opposed to the other logical functions such as and() and or(), is implemented as an m-file.  That's fine, but it is approximately 5X slower than a C++ implementation.  In addition, most modern CPUs have a hardware implementation of xor which it would be nice to piggyback on.

For benchmarking I used the following script


N = 1e4;
N2 = 1e3;

x = zeros (N2,1);
y = ones (N2,1);

bm = zeros (N, 1);
for i = 1:N
  tic;
  #z = xor (x, y);
  #z = or (x, y);
  bm(i) = toc;
endfor

sum (bm)


Times for xor() were about 0.80 seconds while times for the or() function were just 0.16 seconds (5X).  As part of this, xor would drop support for multiple inputs beyond two, but that is okay as Matlab and all of the other logical functions in Octave are limited to two inputs.

Rik <rik5>
Group administrator

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #42926:  xor.diff added by batterylow (3KiB - text/x-patch)
file #42854:  xor1.cc added by batterylow (4KiB - text/x-c++src)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by batterylow (Updated the item)
  • -email is unavailable- added by rik5 (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 2 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2018-01-16 batterylow Attached File- Added xor.diff, #42926
    2018-01-05 batterylow Attached File- Added xor1.cc, #42854

    Back to the top

    Powered by Savane 3.13-758e.
    Corresponding source code