How to speed this up?

This is the place for queries that don't fit in any of the other categories.

Re: How to speed this up?

Postby wavic » Thu Sep 08, 2016 7:17 pm

PyMD5 wrote:Actually, I'm working on that. I found that with a list comprehension, it greatly sped up the process with a small range of IP addresses, but as the list grew, it'd consume all memory and slow to a crawl... so I'm combining my current code with a list comprehension that only runs on a million IP addresses at a time, wrapped in a for loop that increments by one million. If it works, that should just about double the speed of this thing.

Hm! All that indexing... Is there a way to avoid that? Doesn't this slow down the program?
wavic
 
Posts: 165
Joined: Wed May 25, 2016 8:51 pm

Re: How to speed this up?

Postby PyMD5 » Fri Sep 09, 2016 4:45 am

casevh wrote:Here is my attempt at speeding up your worker function. I'm not sure how it compares to your current version.

Code: Select all
from _hashlib import openssl_md5 as md5
import time

def worker(hashinput,range_start,range_end, _md5 = md5):

  aarange = [bytes('%s' % i, 'ascii') for i in range(range_start,range_end)]
  bbrange = [bytes('.%s' % i, 'ascii') for i in range(0, 255)]
  ccrange = [bytes('.%s' % i, 'ascii') for i in range(0, 255)]
  ddrange = [bytes('.%s' % i, 'ascii') for i in range(0, 255)]

  hashin = None

  for aa in aarange:
    temphash = set(hashinput)
    if hashin != temphash:
      hashin = temphash
    if not hashin:
      return
    for bb in bbrange:
      for cc in ccrange:
        temp = aa + bb + cc
        for dd in ddrange:
          h = _md5(temp + dd).hexdigest()
          # h = temp + dd
          if h in hashin:
            hashinput.remove(entry)
            # Print syntax not verified!
            print('Match Found: %s.%s.%s.%s\t%s' % (aa,bb,cc,dd,entry))

if __name__ == '__main__':

  hashlist = [
    '11111111111111111111111111111111', # TEST HASH - replace with your own hashes
    '22222222222222222222222222222222', # TEST HASH - replace with your own hashes
    '33333333333333333333333333333333', # TEST HASH - replace with your own hashes
  ]

  start = time.time()
  worker(hashlist, 0, 3)
  print(time.time() - start)



Ah, genius! I didn't even think of formatting the iterables before using them to generate the MD5 hash, rather than each time the MD5 hash is generated. I'll test that out. I'll use .decode('utf-8') in the print statement to convert the bytes IP addresses back to strings. At least I hope that'll work.

Thanks for the tip on importing _hashlib, too.
PyMD5
 
Posts: 35
Joined: Thu Jun 30, 2016 5:19 am

Re: How to speed this up?

Postby PyMD5 » Fri Sep 09, 2016 4:57 am

wavic wrote:
PyMD5 wrote:Actually, I'm working on that. I found that with a list comprehension, it greatly sped up the process with a small range of IP addresses, but as the list grew, it'd consume all memory and slow to a crawl... so I'm combining my current code with a list comprehension that only runs on a million IP addresses at a time, wrapped in a for loop that increments by one million. If it works, that should just about double the speed of this thing.

Hm! All that indexing... Is there a way to avoid that? Doesn't this slow down the program?


Yeah, it does. In order to keep the list comprehension fast, it has to be really small, which means it's looping through the rest of the code more often, which slows it down... a Catch-22 I couldn't resolve.

I'm trying something else, creating a bunch of MD5 hashes all at once, chucking them into an array, then comparing the known hashes to that array. I'm testing that code now. It's doing about 2 million IP addresses per minute per process right now, but I've got more tweaking to do.

Today I learned how to make multiple commands in a single list comprehension:
[[print('%s\t%s' % (entry1,ipcount+int(entry2[:-32]))),hashinput.remove(entry1)] for entry1 in hashlocal for entry2 in h if entry1 == entry2[-32:]]

That only runs once every two million IP addresses, so it doesn't slow things down much.
PyMD5
 
Posts: 35
Joined: Thu Jun 30, 2016 5:19 am

Re: How to speed this up?

Postby PyMD5 » Sat Sep 10, 2016 3:16 am

casevh wrote:Here is my attempt at speeding up your worker function. I'm not sure how it compares to your current version.

Code: Select all
    if hashin != temphash:
      hashin = temphash



Strange thing, I tried this... and the first time an IP address:MD5 hash match was found (and thus that MD5 hash was removed from the global hash list, and thus the local hash list was updated from the global hash list), it slowed way down to the same speed as though it were processing on a global variable. So I did a work-around where I chuck each item in the global hash list into the local hash list.

Normally, when the IPv4 code is running, my CPU is spiked at 100% all the time on all cores... but when that local hash list updated as you did above, my CPU usage dropped and the processing speed slowed way down... I wonder if that's a bug, where the local hash list is inheriting the global scope of the global hash list.
Last edited by PyMD5 on Sat Sep 10, 2016 4:01 am, edited 1 time in total.
PyMD5
 
Posts: 35
Joined: Thu Jun 30, 2016 5:19 am

Re: How to speed this up?

Postby PyMD5 » Sat Sep 10, 2016 3:27 am

Whoa, that's a pretty good result... the previous IPv4 code ran through the entire IPv4 address space in 50 minutes, 24 seconds for 1 MD5 hash on 8 CPU cores. The new code took 35 minutes, 45 seconds.

Code: Select all
import multiprocessing
from datetime import datetime

def worker(hashglobal,range_start,range_end):
  from _hashlib import openssl_md5 as hashMD5 # Local import is faster
  import sys
  sys.setswitchinterval(.05) # Reduce context switching from 0.005 default to improve performance
  aarange = [bytes('%s' % i, 'ascii') for i in range(range_start,range_end)] # individual iterables for each loop is faster
  bbrange = [bytes('.%s' % i, 'ascii') for i in range(0, 256)]
  ccrange = [bytes('.%s' % i, 'ascii') for i in range(0, 256)]
  ddrange = [bytes('.%s' % i, 'ascii') for i in range(0, 256)]

  hashlocal = [] # local variable is faster, receives the contents of hashinput
  for element in hashglobal:
    hashlocal.append(element)

  for aa in aarange:
    if hashlocal != hashglobal:
      hashlocal = []
      for element in hashglobal:
        hashlocal.append(element)
    if not hashlocal:
      sys.exit(0)
    print('{!s}\rProgress: {:.2%} Hashes: {!s}'.format((" " * 75),(int(aa)-range_start)/(range_end-range_start),len(hashlocal)), end='\r')
    for bb in bbrange:
      aabb = aa+bb
      for cc in ccrange:
        aabbcc = aabb+cc
        for dd in ddrange:
          aabbccdd = aabbcc+dd
          h = hashMD5(aabbccdd).hexdigest()
          [[print('%s\rMatch Found: %s\t%s' % ((" " * 75),str(aabbccdd,'utf-8'),entry)),hashglobal.remove(entry)] for entry in hashlocal if h == entry]

if __name__ == '__main__':
  starttime = datetime.now()
  mgr = multiprocessing.Manager()

  hashlist = [
    '11111111111111111111111111111111', # TEST HASH - replace with your own
    '22222222222222222222222222222222', # TEST HASH - replace with your own
    '33333333333333333333333333333333', # TEST HASH - replace with your own
  ]

  hashinput = mgr.list()
  for item in hashlist:
    hashinput.append(item)

  jobs=[
    multiprocessing.Process(target=worker, args=(hashinput, 0, 32)),
    multiprocessing.Process(target=worker, args=(hashinput, 32, 64)),
    multiprocessing.Process(target=worker, args=(hashinput, 64, 96)),
    multiprocessing.Process(target=worker, args=(hashinput, 96, 128)),
    multiprocessing.Process(target=worker, args=(hashinput, 128, 160)),
    multiprocessing.Process(target=worker, args=(hashinput, 160, 192)),
    multiprocessing.Process(target=worker, args=(hashinput, 192, 224)),
    multiprocessing.Process(target=worker, args=(hashinput, 224, 256)),
  ]

  print('Starting %s processes %s\n\nChecking for %s hashes:' % (len(jobs),datetime.now(),len(hashinput)))
  for entry in hashinput:
    print(entry)
  print('\nResults:')

  for j in jobs:
    j.daemon = False
    j.start()
  for j in jobs:
    j.join()

  endtime = datetime.now()
  print('\nSEARCH COMPLETE, %s duration' % (endtime-starttime))
PyMD5
 
Posts: 35
Joined: Thu Jun 30, 2016 5:19 am

Re: How to speed this up?

Postby casevh » Sat Sep 10, 2016 3:44 am

PyMD5 wrote:
casevh wrote:Here is my attempt at speeding up your worker function. I'm not sure how it compares to your current version.

Code: Select all
    if hashin != temphash:
      hashin = temphash



Strange thing, I tried this... and the first time an IP address:MD5 hash match was found (and thus that MD5 hash was removed from the global hash list, and thus the local hash list was updated from the global hash list), it slowed way down to the same speed as though it were processing on a global variable. So did a work-around where I chuck each item in the global hash list into the local hash list.

Normally, when the IPv4 code is running, my CPU is spiked at 100% all the time on all cores... but when that local hash list updated as you did above, my CPU usage dropped and the processing speed slowed way down... I wonder if that's a bug, where the local hash list is inheriting the global scope of the global hash list.


Untested. Try...

Code: Select all
  if hashin != temphash:
    hashin = temphash[:]
casevh
 
Posts: 114
Joined: Sat Feb 09, 2013 7:35 am

Re: How to speed this up?

Postby PyMD5 » Sat Sep 10, 2016 7:35 pm

casevh wrote:
PyMD5 wrote:
casevh wrote:Here is my attempt at speeding up your worker function. I'm not sure how it compares to your current version.

Code: Select all
    if hashin != temphash:
      hashin = temphash



Strange thing, I tried this... and the first time an IP address:MD5 hash match was found (and thus that MD5 hash was removed from the global hash list, and thus the local hash list was updated from the global hash list), it slowed way down to the same speed as though it were processing on a global variable. So did a work-around where I chuck each item in the global hash list into the local hash list.

Normally, when the IPv4 code is running, my CPU is spiked at 100% all the time on all cores... but when that local hash list updated as you did above, my CPU usage dropped and the processing speed slowed way down... I wonder if that's a bug, where the local hash list is inheriting the global scope of the global hash list.


Untested. Try...
Code: Select all
  if hashin != temphash:
    hashin = temphash[:]



Ah, so by equating the local hash list to the global hash list, it was creating a binding between the local and global, in essence turning the local into a global? IOW, it was just assigning a new name to the existing global, rather than creating a new list.

So the slice will create a shallow copy, which would prevent that.

That does seem to be "buggy" to me... if one requests that an existing local scope list be updated from a global scope list, one should expect that local scope list to remain local scope.
PyMD5
 
Posts: 35
Joined: Thu Jun 30, 2016 5:19 am

Re: How to speed this up?

Postby Ofnuts » Sat Sep 10, 2016 11:29 pm

PyMD5 wrote:That does seem to be "buggy" to me... if one requests that an existing local scope list be updated from a global scope list, one should expect that local scope list to remain local scope.


Nope. In Python, what is "local" is the name. Period.

https://www.youtube.com/watch?v=_AEJHKGk9ns
This forum has been moved to http://python-forum.io/. See you there.
User avatar
Ofnuts
 
Posts: 2659
Joined: Thu May 14, 2015 9:46 am
Location: Paris, France, EU, Earth, Solar system, Milky Way, Local Cluster, Universe #32987440940987

Re: How to speed this up?

Postby PyMD5 » Sun Sep 11, 2016 1:40 am

Ofnuts wrote:
PyMD5 wrote:That does seem to be "buggy" to me... if one requests that an existing local scope list be updated from a global scope list, one should expect that local scope list to remain local scope.


Nope. In Python, what is "local" is the name. Period.

https://www.youtube.com/watch?v=_AEJHKGk9ns


Weird. Why does referencing a global run so slowly, then? Shouldn't all variables be referenced equally fast? Is it because Python resolves variables LEGB?
PyMD5
 
Posts: 35
Joined: Thu Jun 30, 2016 5:19 am

Re: How to speed this up?

Postby PyMD5 » Wed Sep 14, 2016 3:26 am

Ok, I can't get the IPv6 code to go over 2 million IP addresses per minute per process no matter what I do. So I figured out how to get Numpy installed.

First, I downloaded the numpy-1.11.2rc1+mkl-cp35-cp35m-win_amd64.whl from http://www.lfd.uci.edu/~gohlke/pythonlibs/#numpy, and moved it into the Python\Python36\Scripts directory, then I started an Administrator CMD prompt, changed directory to Python\Python36\Scripts, and typed:
pip3.6 install {PATH ELIDED}\Python\Python36\Scripts\numpy-1.11.2rc1+mkl-cp35-cp35m-win_amd64.whl

(Ignore the {PATH ELIDED}, that's just my way of shortening the long path to the Python directory.)

It gave the error:
numpy-1.11.2rc1+mkl-cp35-cp35m-win_amd64.whl is not a supported wheel on this platform.

So I changed the file name to numpy-1.11.2rc1+mkl-cp36-cp36m-win_amd64.whl and tried again. It installed.

Now I have to learn how to create a two-dimensional array in Numpy and compare each element of the the first dimension with each element of the second dimension.
PyMD5
 
Posts: 35
Joined: Thu Jun 30, 2016 5:19 am

Re: How to speed this up?

Postby wavic » Wed Sep 14, 2016 8:51 pm

Numpy or SciPy is the way to go further. I think I mentioned it here before. People do amasing things with those ones. I can't. For now :twisted:
What if instead of lists you use some other data type. To avoid indexing. Also is it posible in ram data bases like redis or something else to improve the code. Querying the data base is extremely fast. Far more then iterating lists. I think so. May be I am wrong
wavic
 
Posts: 165
Joined: Wed May 25, 2016 8:51 pm

Re: How to speed this up?

Postby PyMD5 » Sun Sep 25, 2016 4:38 am

I'm checking out PyParallel right now. I tried joblib, but it's essentially a wrapper for multiprocessing. I couldn't figure out how to get Numpy to work, but I'm still working on it.

One thing I noticed... the ipaddress module used for the IPv6 code is written entirely in Python, with no calls to C code... I'm wondering if I convert ipaddress.py to c, then to a .pyd file, if that'd speed it up? It'd be nice if the IPv6 code was doing ~4 billion IP addresses in ~35 minutes like the IPv4 code.
PyMD5
 
Posts: 35
Joined: Thu Jun 30, 2016 5:19 am

Re: How to speed this up?

Postby PyMD5 » Mon Sep 26, 2016 4:07 am

Ok, Trent Nelson's PyParallel isn't going to work... it uses thread-safe code for any multi-core processing, thus it can't print from a sub-routine, the same problem experienced by the CPython IDLE, which is why I went to running the code from a CMD prompt.

In addition, the garbage collection scheme of PyParallel is more tuned for short-runtime processes. In one of Trent's presentations, he specifically says:
Code: Select all
For instance, you couldn't do something like this:

for x in range(0,1000000000):
  ...

But why would you?!


Well, I can think of one reason. Heh.

So, I'm focusing on speeding up the ipaddress.IPv6Address module, since that's what's slowing down the IPv6 code right now. The IPv4 code is about as fast as I can make it, it's utilizing 100% of all cores and can chuck through ~4 billion IP addresses in ~35 minutes, so that's not bad.
PyMD5
 
Posts: 35
Joined: Thu Jun 30, 2016 5:19 am

Previous

Return to General Coding Help

Who is online

Users browsing this forum: Bing [Bot] and 9 guests