Re: [petsc-users] PetscTableCreateHashSize

[Satish Balay]

With configure option:   --with-ctable=

Satish

On Tue, 10 Jan 2017, Kong, Fande wrote:

> BTW, one more question:
> 
> There are some pieces of code in #if defined(PETSC_USE_CTABLE)  #endif.
> How to disable ctable? That is, make PETSC_USE_CTABLE false during
> configuration.
> 
> Fande,
> 
> On Tue, Jan 10, 2017 at 12:33 AM, Jed Brown  wrote:
> 
> > Satish Balay  writes:
> > > I tried looking at it - but it was easier for me to fixup current ctable
> > code.
> >
> > I mentioned it more as a long-term thing.  I don't think we need two
> > different hashtable implementations in PETSc.  I think khash is better
> > and extensible, so we may as well use it in all new code and migrate
> > petsctable to it when convenient.  I don't think it's urgent unless
> > someone has a use case that needs it.
> >
> 

Re: [petsc-users] PetscTableCreateHashSize

[Kong, Fande]

BTW, one more question:

There are some pieces of code in #if defined(PETSC_USE_CTABLE)  #endif.
How to disable ctable? That is, make PETSC_USE_CTABLE false during
configuration.

Fande,

On Tue, Jan 10, 2017 at 12:33 AM, Jed Brown  wrote:

> Satish Balay  writes:
> > I tried looking at it - but it was easier for me to fixup current ctable
> code.
>
> I mentioned it more as a long-term thing.  I don't think we need two
> different hashtable implementations in PETSc.  I think khash is better
> and extensible, so we may as well use it in all new code and migrate
> petsctable to it when convenient.  I don't think it's urgent unless
> someone has a use case that needs it.
>

Re: [petsc-users] PetscTableCreateHashSize

[Jed Brown]

Satish Balay  writes:
> I tried looking at it - but it was easier for me to fixup current ctable code.

I mentioned it more as a long-term thing.  I don't think we need two
different hashtable implementations in PETSc.  I think khash is better
and extensible, so we may as well use it in all new code and migrate
petsctable to it when convenient.  I don't think it's urgent unless
someone has a use case that needs it.


signature.asc
Description: PGP signature

Re: [petsc-users] PetscTableCreateHashSize

[Satish Balay]

On Mon, 9 Jan 2017, Jed Brown wrote:

> Satish Balay  writes:
> 
> >> Why is it not sufficient to be coprime?
> >
> > Well whatever was implemented previsously with PETSC_HASH_FACT [a
> > prime number] didn't work well. [there were a couple of reports on it].
> 
> That was linear probing, right?

yes - but not sure if it implemented a good hash function. [had issues with 
collisions]

> 
> > Checking double hashing [Intro to algorithms, Coremen et all.]:
> >
> > For a hashtable size 'm' - and using hash functions h1(k), h2(k) - it
> > says: h2(k) must be relatively prime to 'm'. [for all possilbe 'k'
> > values? its not clear. Also any constraints on h1(k)?]
> 
> relatively prime = coprime
> 
> > And it suggested the following as one way to imlement:
> > choose a prime 'm'
> > h1(k) = k mod m
> > h2(k) = 1 +  (k mod m')

Forgot to mention: choose m' = (m-1) or (m-2)

> >
> > This was simple enough for me - so I updated ctable to use it. I've
> > added entries up to INT_MAX.
> 
> Thanks.
> 
> > If its still lacking (I could potentially add more entries - perhaps
> > for 64bitincides? or) - feel free to change the algorithm for arbirary
> > sizes...
> 
> I would use khash (hash.h) because it is a portable and well-optimized
> hash implementation.  The version in PETSc uses primes and double
> hashing, though upstream now uses quadratic probing (better cache
> locality).

I tried looking at it - but it was easier for me to fixup current ctable code.

Satish

Re: [petsc-users] PetscTableCreateHashSize

[Jed Brown]

Satish Balay  writes:

>> Why is it not sufficient to be coprime?
>
> Well whatever was implemented previsously with PETSC_HASH_FACT [a
> prime number] didn't work well. [there were a couple of reports on it].

That was linear probing, right?

> Checking double hashing [Intro to algorithms, Coremen et all.]:
>
> For a hashtable size 'm' - and using hash functions h1(k), h2(k) - it
> says: h2(k) must be relatively prime to 'm'. [for all possilbe 'k'
> values? its not clear. Also any constraints on h1(k)?]

relatively prime = coprime

> And it suggested the following as one way to imlement:
> choose a prime 'm'
> h1(k) = k mod m
> h2(k) = 1 +  (k mod m')
>
> This was simple enough for me - so I updated ctable to use it. I've
> added entries up to INT_MAX.

Thanks.

> If its still lacking (I could potentially add more entries - perhaps
> for 64bitincides? or) - feel free to change the algorithm for arbirary
> sizes...

I would use khash (hash.h) because it is a portable and well-optimized
hash implementation.  The version in PETSc uses primes and double
hashing, though upstream now uses quadratic probing (better cache
locality).


signature.asc
Description: PGP signature

Re: [petsc-users] PetscTableCreateHashSize

[Satish Balay]

On Mon, 9 Jan 2017, Jed Brown wrote:

> Satish Balay  writes:
> 
> > On Mon, 9 Jan 2017, Jed Brown wrote:
> >
> >> Satish Balay  writes:
> >> > Sure - I'm using a crappy algorithm [look-up table] to get
> >> > "prime_number_close_to(1.4*sz)" - as I don't know how to generate
> >> > these numbers automatically.
> >> 
> >> FWIW, it only needs to be coprime with PETSC_HASH_FACT.
> >
> > Not sure I understand - are you saying coprime requirement is easier
> > satisfy than a single prime?
> 
> Yeah, just don't be a multiple of PETSC_HASH_FACT, which is itself
> prime.
> 
> > I had switched this code to use double-hasing algorithm - and the
> > requirement here is - the table size be a prime number. [so I'm
> > attempting to estimate a prime number suitable for the table size]
> 
> Why is it not sufficient to be coprime?

Well whatever was implemented previsously with PETSC_HASH_FACT [a
prime number] didn't work well. [there were a couple of reports on it].

Checking double hashing [Intro to algorithms, Coremen et all.]:

For a hashtable size 'm' - and using hash functions h1(k), h2(k) - it
says: h2(k) must be relatively prime to 'm'. [for all possilbe 'k'
values? its not clear. Also any constraints on h1(k)?]

And it suggested the following as one way to imlement:
choose a prime 'm'
h1(k) = k mod m
h2(k) = 1 +  (k mod m')

This was simple enough for me - so I updated ctable to use it. I've
added entries up to INT_MAX.

If its still lacking (I could potentially add more entries - perhaps
for 64bitincides? or) - feel free to change the algorithm for arbirary
sizes...

Satish

Re: [petsc-users] PetscTableCreateHashSize

[Satish Balay]

I've added up to INT_MAX

Let us know if that doesn't work.

Satish

On Mon, 9 Jan 2017, Kong, Fande wrote:

> Thanks a lot Satish!
> 
> Like Jed said, it would be better if we could come up an algorithm for
> automatically computing a hash size for a given n.  Otherwise, we  may need
> to  add more entries to the lookup again in the future.
> 
> Fande,
> 
> On Mon, Jan 9, 2017 at 2:14 PM, Satish Balay  wrote:
> 
> > On Mon, 9 Jan 2017, Jed Brown wrote:
> >
> > > Satish Balay  writes:
> > > > Sure - I'm using a crappy algorithm [look-up table] to get
> > > > "prime_number_close_to(1.4*sz)" - as I don't know how to generate
> > > > these numbers automatically.
> > >
> > > FWIW, it only needs to be coprime with PETSC_HASH_FACT.
> >
> > Not sure I understand - are you saying coprime requirement is easier
> > satisfy than a single prime?
> >
> > I had switched this code to use double-hasing algorithm - and the
> > requirement here is - the table size be a prime number. [so I'm
> > attempting to estimate a prime number suitable for the table size]
> >
> > I pushed the following
> > https://urldefense.proofpoint.com/v2/url?u=https-3A__
> > bitbucket.org_petsc_petsc_commits_d742c75fd0d514f7fa1873d5b10984
> > bc3f363031=DQIBAg=54IZrppPQZKX9mLzcGdPfFD1hxrcB_
> > _aEkJFOKJFd00=DUUt3SRGI0_JgtNaS3udV68GRkgV4ts7XKfj2opmi
> > CY=nkPXHuaxZeHPzOteY25j_Dptk5XyWiqwzaJbEwI5uWY=
> > eOjfGCXP3g18VLYhXY5xrlOr7AFn7o3G_YrYVo8Rw8Y=
> >
> > Satish
> >
> 

Re: [petsc-users] PetscTableCreateHashSize

[Jed Brown]

Satish Balay  writes:

> On Mon, 9 Jan 2017, Jed Brown wrote:
>
>> Satish Balay  writes:
>> > Sure - I'm using a crappy algorithm [look-up table] to get
>> > "prime_number_close_to(1.4*sz)" - as I don't know how to generate
>> > these numbers automatically.
>> 
>> FWIW, it only needs to be coprime with PETSC_HASH_FACT.
>
> Not sure I understand - are you saying coprime requirement is easier
> satisfy than a single prime?

Yeah, just don't be a multiple of PETSC_HASH_FACT, which is itself
prime.

> I had switched this code to use double-hasing algorithm - and the
> requirement here is - the table size be a prime number. [so I'm
> attempting to estimate a prime number suitable for the table size]

Why is it not sufficient to be coprime?


signature.asc
Description: PGP signature

Re: [petsc-users] PetscTableCreateHashSize

[Kong, Fande]

Thanks a lot Satish!

Like Jed said, it would be better if we could come up an algorithm for
automatically computing a hash size for a given n.  Otherwise, we  may need
to  add more entries to the lookup again in the future.

Fande,

On Mon, Jan 9, 2017 at 2:14 PM, Satish Balay  wrote:

> On Mon, 9 Jan 2017, Jed Brown wrote:
>
> > Satish Balay  writes:
> > > Sure - I'm using a crappy algorithm [look-up table] to get
> > > "prime_number_close_to(1.4*sz)" - as I don't know how to generate
> > > these numbers automatically.
> >
> > FWIW, it only needs to be coprime with PETSC_HASH_FACT.
>
> Not sure I understand - are you saying coprime requirement is easier
> satisfy than a single prime?
>
> I had switched this code to use double-hasing algorithm - and the
> requirement here is - the table size be a prime number. [so I'm
> attempting to estimate a prime number suitable for the table size]
>
> I pushed the following
> https://urldefense.proofpoint.com/v2/url?u=https-3A__
> bitbucket.org_petsc_petsc_commits_d742c75fd0d514f7fa1873d5b10984
> bc3f363031=DQIBAg=54IZrppPQZKX9mLzcGdPfFD1hxrcB_
> _aEkJFOKJFd00=DUUt3SRGI0_JgtNaS3udV68GRkgV4ts7XKfj2opmi
> CY=nkPXHuaxZeHPzOteY25j_Dptk5XyWiqwzaJbEwI5uWY=
> eOjfGCXP3g18VLYhXY5xrlOr7AFn7o3G_YrYVo8Rw8Y=
>
> Satish
>

Re: [petsc-users] PetscTableCreateHashSize

[Satish Balay]

On Mon, 9 Jan 2017, Jed Brown wrote:

> Satish Balay  writes:
> > Sure - I'm using a crappy algorithm [look-up table] to get
> > "prime_number_close_to(1.4*sz)" - as I don't know how to generate
> > these numbers automatically.
> 
> FWIW, it only needs to be coprime with PETSC_HASH_FACT.

Not sure I understand - are you saying coprime requirement is easier
satisfy than a single prime?

I had switched this code to use double-hasing algorithm - and the
requirement here is - the table size be a prime number. [so I'm
attempting to estimate a prime number suitable for the table size]

I pushed the following
https://bitbucket.org/petsc/petsc/commits/d742c75fd0d514f7fa1873d5b10984bc3f363031

Satish

Re: [petsc-users] PetscTableCreateHashSize

[Jed Brown]

Satish Balay  writes:
> Sure - I'm using a crappy algorithm [look-up table] to get
> "prime_number_close_to(1.4*sz)" - as I don't know how to generate
> these numbers automatically.

FWIW, it only needs to be coprime with PETSC_HASH_FACT.


signature.asc
Description: PGP signature

Re: [petsc-users] PetscTableCreateHashSize

[Satish Balay]

On Mon, 9 Jan 2017, Jed Brown wrote:

> Satish Balay  writes:
> 
> > We can add more entries to the lookup. The stack below looks
> > incomplete. Which routine is calling PetscTableCreateHashSize() with
> > this big size?
> >
> > Satish
> >
> > ---
> > $ git diff
> > diff --git a/src/sys/utils/ctable.c b/src/sys/utils/ctable.c
> > index cd64284..761a2c6 100644
> > --- a/src/sys/utils/ctable.c
> > +++ b/src/sys/utils/ctable.c
> > @@ -25,6 +25,7 @@ static PetscErrorCode PetscTableCreateHashSize(PetscInt 
> > sz, PetscInt *hsz)
> >else if (sz < 819200)  *hsz = 1193557;
> >else if (sz < 1638400) *hsz = 2297059;
> >else if (sz < 3276800) *hsz = 4902383;
> > +  else if (sz < 6553600) *hsz = 9179113;
> 
> Does anyone else think this is ridiculous?  Why not either generate the
> hash sizes algorithmically or put in enough for MAXINT?

Sure - I'm using a crappy algorithm [look-up table] to get
"prime_number_close_to(1.4*sz)" - as I don't know how to generate
these numbers automatically.

Will add more entries to this lookup table.

Satish

Re: [petsc-users] PetscTableCreateHashSize

[Jed Brown]

Satish Balay  writes:

> We can add more entries to the lookup. The stack below looks
> incomplete. Which routine is calling PetscTableCreateHashSize() with
> this big size?
>
> Satish
>
> ---
> $ git diff
> diff --git a/src/sys/utils/ctable.c b/src/sys/utils/ctable.c
> index cd64284..761a2c6 100644
> --- a/src/sys/utils/ctable.c
> +++ b/src/sys/utils/ctable.c
> @@ -25,6 +25,7 @@ static PetscErrorCode PetscTableCreateHashSize(PetscInt sz, 
> PetscInt *hsz)
>else if (sz < 819200)  *hsz = 1193557;
>else if (sz < 1638400) *hsz = 2297059;
>else if (sz < 3276800) *hsz = 4902383;
> +  else if (sz < 6553600) *hsz = 9179113;

Does anyone else think this is ridiculous?  Why not either generate the
hash sizes algorithmically or put in enough for MAXINT?


signature.asc
Description: PGP signature

Re: [petsc-users] PetscTableCreateHashSize

[Kong, Fande]

Thanks, Satish,


On Mon, Jan 9, 2017 at 12:36 PM, Satish Balay  wrote:

> We can add more entries to the lookup. The stack below looks
> incomplete. Which routine is calling PetscTableCreateHashSize() with
> this big size?
>

call trace:

[4]PETSC ERROR: #3 MatSetUpMultiply_MPIAIJ() line 36 in
/home/schuseba/projects/64_bit_builds/petsc/src/mat/impls/aij/mpi/mmaij.c

[9]PETSC ERROR: #4 MatAssemblyEnd_MPIAIJ() line 747 in
/home/schuseba/projects/64_bit_builds/petsc/src/mat/impls/aij/mpi/mpiaij.c

[9]PETSC ERROR: #4 MatAssemblyEnd_MPIAIJ() line 747 in
/home/schuseba/projects/64_bit_builds/petsc/src/mat/impls/aij/mpi/mpiaij.c


>
> Satish
>
> ---
> $ git diff
> diff --git a/src/sys/utils/ctable.c b/src/sys/utils/ctable.c
> index cd64284..761a2c6 100644
> --- a/src/sys/utils/ctable.c
> +++ b/src/sys/utils/ctable.c
> @@ -25,6 +25,7 @@ static PetscErrorCode PetscTableCreateHashSize(PetscInt
> sz, PetscInt *hsz)
>else if (sz < 819200)  *hsz = 1193557;
>else if (sz < 1638400) *hsz = 2297059;
>else if (sz < 3276800) *hsz = 4902383;
> +  else if (sz < 6553600) *hsz = 9179113;
>else SETERRQ1(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"A really huge
> hash is being requested.. cannot process: %D",sz);
>PetscFunctionReturn(0);
>  }
>
> On Mon, 9 Jan 2017, Kong, Fande wrote:
>
> > Hi All,
> >
> > Hash size is set manually according to the number of expected keys in the
> > function PetscTableCreateHashSize(). Any reason to restrict the
> > ``n"<3276800?
> >
> > One user here encountered an issue because of this restriction. The
> > messages are as follows:
> >
> > [3]PETSC ERROR: - Error Message
> > --
> >
> > [3]PETSC ERROR: Argument out of range
> >
> > [3]PETSC ERROR: A really huge hash is being requested.. cannot process:
> > 3497472
> >
> > [3]PETSC ERROR: See https://urldefense.proofpoint.
> com/v2/url?u=http-3A__www.mcs.anl.gov_petsc_documentation_
> faq.html=DQIBAg=54IZrppPQZKX9mLzcGdPfFD1hxrcB_
> _aEkJFOKJFd00=DUUt3SRGI0_JgtNaS3udV68GRkgV4ts7XKfj2opmiCY=
> fvlOBYaS6Bzg7U320hXOmDVca3d6OkyJnp56sjG6pG8=
> Rp5eqZDYZPxEHWb7SoQwATm41rJPVIolrCKuUGdM72U=  for
> > trouble shooting.
> >
> > [3]PETSC ERROR: Petsc Release Version 3.7.4, unknown
> >
> > [3]PETSC ERROR: /home/schuseba/projects/64_bit_builds/yak/yak-opt on a
> > linux-gnu-c-opt named r3i3n0 by schuseba Fri Jan  6 23:15:37 2017
> >
> > [3]PETSC ERROR: Configure options --download-hypre=1 --with-ssl=0
> > --with-debugging=no --with-pic=1 --with-shared-libraries=1
> > --with-64-bit-indices=1 --with-cc=mpicc --with-cxx=mpicxx
> --with-fc=mpif90
> > --download-metis=1 --download-parmetis=1 --download-fblaslapack=1
> > --download-superlu_dist=1 -CC=mpicc -CXX=mpicxx -FC=mpif90 -F77=mpif77
> > -F90=mpif90 -CFLAGS="-fPIC -fopenmp" -CXXFLAGS="-fPIC -fopenmp"
> > -FFLAGS="-fPIC -fopenmp" -FCFLAGS="-fPIC -fopenmp" -F90FLAGS="-fPIC
> > -fopenmp" -F77FLAGS="-fPIC -fopenmp"
> >
> > [3]PETSC ERROR: #1 PetscTableCreateHashSize() line 28 in
> > /home/schuseba/projects/64_bit_builds/petsc/src/sys/utils/ctable.c
> >
> >
> >
> >
> >
> > Fande,
> >
>
>

Re: [petsc-users] PetscTableCreateHashSize

[Satish Balay]

We can add more entries to the lookup. The stack below looks
incomplete. Which routine is calling PetscTableCreateHashSize() with
this big size?

Satish

---
$ git diff
diff --git a/src/sys/utils/ctable.c b/src/sys/utils/ctable.c
index cd64284..761a2c6 100644
--- a/src/sys/utils/ctable.c
+++ b/src/sys/utils/ctable.c
@@ -25,6 +25,7 @@ static PetscErrorCode PetscTableCreateHashSize(PetscInt sz, 
PetscInt *hsz)
   else if (sz < 819200)  *hsz = 1193557;
   else if (sz < 1638400) *hsz = 2297059;
   else if (sz < 3276800) *hsz = 4902383;
+  else if (sz < 6553600) *hsz = 9179113;
   else SETERRQ1(PETSC_COMM_SELF,PETSC_ERR_ARG_OUTOFRANGE,"A really huge hash 
is being requested.. cannot process: %D",sz);
   PetscFunctionReturn(0);
 }

On Mon, 9 Jan 2017, Kong, Fande wrote:

> Hi All,
> 
> Hash size is set manually according to the number of expected keys in the
> function PetscTableCreateHashSize(). Any reason to restrict the
> ``n"<3276800?
> 
> One user here encountered an issue because of this restriction. The
> messages are as follows:
> 
> [3]PETSC ERROR: - Error Message
> --
> 
> [3]PETSC ERROR: Argument out of range
> 
> [3]PETSC ERROR: A really huge hash is being requested.. cannot process:
> 3497472
> 
> [3]PETSC ERROR: See http://www.mcs.anl.gov/petsc/documentation/faq.html for
> trouble shooting.
> 
> [3]PETSC ERROR: Petsc Release Version 3.7.4, unknown
> 
> [3]PETSC ERROR: /home/schuseba/projects/64_bit_builds/yak/yak-opt on a
> linux-gnu-c-opt named r3i3n0 by schuseba Fri Jan  6 23:15:37 2017
> 
> [3]PETSC ERROR: Configure options --download-hypre=1 --with-ssl=0
> --with-debugging=no --with-pic=1 --with-shared-libraries=1
> --with-64-bit-indices=1 --with-cc=mpicc --with-cxx=mpicxx --with-fc=mpif90
> --download-metis=1 --download-parmetis=1 --download-fblaslapack=1
> --download-superlu_dist=1 -CC=mpicc -CXX=mpicxx -FC=mpif90 -F77=mpif77
> -F90=mpif90 -CFLAGS="-fPIC -fopenmp" -CXXFLAGS="-fPIC -fopenmp"
> -FFLAGS="-fPIC -fopenmp" -FCFLAGS="-fPIC -fopenmp" -F90FLAGS="-fPIC
> -fopenmp" -F77FLAGS="-fPIC -fopenmp"
> 
> [3]PETSC ERROR: #1 PetscTableCreateHashSize() line 28 in
> /home/schuseba/projects/64_bit_builds/petsc/src/sys/utils/ctable.c
> 
> 
> 
> 
> 
> Fande,
>