Re: [eigen] Vectorized Hamming distance

[Benoit Jacob <jacob.benoit.1@xxxxxxxxx>]

2009/11/25 rodrigo benenson <rodrigo.benenson@xxxxxxxxx>:
> Hello,
> I would like to use the Eigen librabry to write a vectorized (using
> SIMD instruction) version of the Hamming Distance between two
> Matrix<int, N, 1>.
> (following the spirit of Benoît Jacob's "Eigen2 as a vectorization
> library" blog post)

Coincidentally, the current thread "true Array support" is exactly about that.

>
> The hamming distance consists on doing XOR between two vectors and
> then counting the number of bits in the resulting vector.
>
> Any suggestion on how to do this ?
>
> Why is it that Eigen does not support boolean operations on int data types ?
>
> Anyone has tried something similar before ?

I don't recall any use case appearing before today, that's probably
why we don't have it. But with the increasing number of people using
Eigen with integer types, that seems like a reasonable feature
addition. And actually we already have the SIMD support for xor:
ei_pxor(a,b) in the development branch.

How to do this:

First of all I assume the development branch, not 2.0. It's not much
different, it's just that it already has SIMD xor support.

First see how to implement a custom binary operator:

http://eigen.tuxfamily.org/dox-devel/classEigen_1_1MatrixBase.html#ae022bf30f910d5d1b016c3d88f6af1ad

Then see this page:
http://eigen.tuxfamily.org/dox/CustomizingEigen.html#ExtendingMatrixBase
about how to add a new method in MatrixBase from outside Eigen, by
defining EIGEN_MATRIXBASE_PLUGIN. You can also put it in Cwise if you
want a cwise() syntax, using EIGEN_CWISE_PLUGIN. And your functor
should go in EIGEN_FUNCTORS_PLUGIN.

Then have a look at other functors to see how SIMD is done, for
example look at ei_scalar_sum_op in Core/Functors.h:

for example here's how division is implemented:

template<typename Scalar> struct ei_scalar_quotient_op EIGEN_EMPTY_STRUCT {
  EIGEN_STRONG_INLINE const Scalar operator() (const Scalar& a, const
Scalar& b) const { return a / b; }
  template<typename PacketScalar>
  EIGEN_STRONG_INLINE const PacketScalar packetOp(const PacketScalar&
a, const PacketScalar& b) const
  { return ei_pdiv(a,b); }
};
template<typename Scalar>
struct ei_functor_traits<ei_scalar_quotient_op<Scalar> > {
  enum {
    Cost = 2 * NumTraits<Scalar>::MulCost,
    PacketAccess = ei_packet_traits<Scalar>::size>1
                  #if (defined EIGEN_VECTORIZE_SSE)
                  && NumTraits<Scalar>::HasFloatingPoint
                  #endif
  };
};

You can see that basically SIMD is implemented in the packetOp()
method, and setting PacketAccess to 1 in the ei_functor_traits.

So in your case you'd use ei_pxor instead of ei_pdiv, and that's it.

Benoit





>
> Regards,
> rodrigob.
>
>
>