Why don’t you want all the password entries in memory - 1M entries is probably only a few MB’s and most machines have GBytes of memory.

If all the entries are not in memory then getting the file content into your program will be an I/O bottleneck.

If you do this on a modern machine the OS will cache the files anyway, so they will be in memory - but it would be better to do build you own hash table that repeated thash the I/O system and garbage collector.

Put the password entries in a hash table (say ets) and do a hash lookup no search is involved - this is O(1) and independent of the number of entries in the table.

And yes the hash table takes space (a few MB) but not using a hash table takes space (in memory buffers in the OS) and puts repeated pressure on the I/O and GC

The best way is to read the entire file atomically, split it into lines and inject them into a resident hash table.

I guess I’ve assumed that you want to check passwords often and read the big table infrequently. If you only onto to check one password every few hours then it’s irrelevant how you do it since anything you write will be sufficiently fast.

If you want to check thousands of passwords per second then you must build an in-memory hash table.

It all depends upon what you want to do

I’ve just tried sqlite on 1M passwords (not 10M) and can now directly compare with ets.

Name       Build (sec)   FileSize (MB)  Lookup Time (micro sec) 
ets        0.68          24             0.455 
sqlite3    719           41             53

Build is the time to build the ets table (or sqlite3) database the FileSize is the on-disk size of the ets-table/database Time is the lookup time (microseconds)

I suspect that the differences are due to the fact that ets is in memory and I understand what I’m doing, whereas the sqlite table is on disk and I haven’t a clue what I’m doing - it’s my first attempt at using sqlite so I’m probably doing it all wrong. Even if sqlite is in memory for the lookups there are an awful lot of round-trips between Erlang and sqlite and there is a semantic mismatch between the internal representations of data in Erlang and sqlite and conversion always takes time.

aside: First time I got sqlite working as well, so I’m quite pleased.

It’s basically (in SQL)

 create table test (pwd text primary key); 
 insert into test values ('password1);
 insert into test values ('password2);
 insert into test values ('password3);
  ...
 insert into test values ('password1000000');

then to lookup

 select * from test where pwd='something'

Seems to work - but rather slow.

What is more disturbing is the memory usage - 30 MB for 1M passwords would indicate 300MB for 10M passwords - now 300MB is getting to the point where I worry about space efficiency. So while a hash table is fastest it’s not space efficient - I suspect that bloom filters might be the way to go.

Just for fun I did this in Erlang - the code and arguments are pretty much the same for Elixir

First I read the password file, split it into lines and insert into an ets table and dump the ets table. Note: these file-at-a-time operations are by far the most efficient way to get data into and out of the system.

build() ->
    {ok, B} = file:read_file("10-million-password-list-top-1000000.txt"),
    Parts = binary:split(B,<<"\n">>,[global]),
    Tab = ets:new(passwords,[]),
    [ets:insert(Tab,{I,[]}) || I<- Parts],
    ets:tab2file(Tab, "passwords.tab").

It doesn’t matter how long this takes since I only do it once.

To check a password we read the table back into memory and do a lookup

lookup(Password) ->    
    {ok, Tab} = ets:file2tab("passwords.tmp"),
    case ets:lookup(Tab, Password) of
    [] -> false;
    _  -> true
    end.

I can’t think of a faster way to do this.

Now for some timings - I measured the time to do ets:file2tab this was 0.75 seconds
I timed the lookups by looking up every password in the list - this took 0.4 microseconds per lookup. (this is on a 3.1GHz Intel Core i7 macbook pro) so you could check 2.2 Million passwords/second.

Reading the password file takes 0.75 seconds so the “read file” + single check could do 4800 passwords per hour and you’d be transferring about 40 GBytes of data per hour into your program - That might be acceptable - it depends what else you are doing. It will use a fair bit of CPU reading the ets file.

Keeping your ets table in memory costs virtually nothing (in terms of GC) - you don’t need a gen server to access it since ets tables are shared anyway.

Hi, I had similar problem and after some benchmarking I found out that the fastest way for me was to store sorted data in ETS and use binary search. Here is an example https://gist.github.com/alukasz/7dcf1dc097e321565c372dc0de5ea1fe

Name                          ips        average  deviation         median         99th %
ETS + binary search       24.14 K      0.0414 ms    ±15.77%      0.0400 ms      0.0690 ms
stream + filter         0.00162 K      616.14 ms     ±5.05%      622.06 ms      641.31 ms

Comparison: 
ETS + binary search       24.14 K
stream + filter         0.00162 K - 14876.58x slower

I mentioned Postgres being a reasonable choice for a broad variety of problems, so I figured I’d back it up. Results first:

# these benchmarks made with Benchee

clark$> PORT=4000 MIX_ENV=prod mix run bench.exs
mixwarning: found quoted keyword "test" but the quotes are not required. Note that keywords are always atoms, even when quoted, and quotes should only be used to introduce keywords with foreign characters in them
  mix.exs:58

Operating System: macOS"
CPU Information: Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
Number of Available Cores: 12
Available memory: 16 GB
Elixir 1.7.3
Erlang 21.1

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 5 s
memory time: 0 μs
parallel: 1
inputs: none specified
Estimated total run time: 14 s


Benchmarking check password ecto query builder...
Benchmarking check password postgrex prepared...

Name                                        ips        average  deviation         median         99th %
check password postgrex prepared        10.12 K       98.79 μs    ±10.25%          96 μs         139 μs
check password ecto query builder        8.47 K      118.04 μs    ±11.38%         114 μs         169 μs

Comparison: 
check password postgrex prepared        10.12 K
check password ecto query builder        8.47 K - 1.19x slower
warning: unused import Ecto.Query
  bench.exs:1

Next, benchmark setup:

import Ecto.Query                                                                                       
                                                                                                        
query_prepared = "SELECT id FROM passwords WHERE password = $1"                                         
                                                                                                        
{:ok, _pid} =                                                                                           
  Postgrex.start_link(hostname: "localhost", username: "clark", password: "", database: "passtest_dev", 
pool: DBConnection.Poolboy, pool_size: 20, name: DB)                                                    
                                                                                                        
{:ok, prepared} = Postgrex.prepare(DB, "get_password", query_prepared, pool: DBConnection.Poolboy)      
                                                                                                        
Benchee.run(%{                                                                                          
  "check password ecto query builder" => fn ->                                                          
    Ecto.Query.select("passwords", [p], p.id)                                                           
    |> Ecto.Query.where([p], p.password == "austin")                                                    
    |> Passtest.Repo.one!                                                                               
  end,                                                                                                  
  "check password postgrex prepared" => fn ->                                                           
     Postgrex.execute!(DB, prepared, ["austin"], pool: DBConnection.Poolboy)                            
  end                                                                                                   
})

I generated a standard phoenix app, created a database, and then ran this migration:

defmodule Passtest.Repo.Migrations.CreatePasswords do                                                   
  use Ecto.Migration                                                                                    
                                                                                                        
  def change do                                                                                         
    create table("passwords") do                                                                        
      add :password, :string, size: 50                                                                  
    end                                                                                                 
                                                                                                        
    create index("passwords", [:password])                                                              
  end                                                                                                   
end  

The data file I used was the 1M passwords one from the link posted earlier in the thread:

clark$> wc -l ~/code/pass.txt
999999 /Users/clark/code/pass.txt

clark$> head -10 ~/code/pass.txt
123456
password
12345678
qwerty
123456789
12345
1234
111111
1234567
dragon

To be transparent, the above is with BEAM and the Postgres server instance running on my local machine. This decreases latency vs what you would experience in a production setting where databases and app servers live on their own physical/virtual hardware separated by at least one network hop. Even so, starting from a baseline 99%ile of 139 μs is encouraging. For something that isn’t a hot loop, 139 μs is blisteringly low latency. Especially something where network time is going to dominate computation time by one or two orders of magnitude.

I’m going to paraphrase a comment I read elsewhere that was put forward in a similar context: performance is rarely about what is theoretically possible. It’s almost always a function of what you can achieve with the time and resources you have available. Further, it’s a function of what is necessary for the situation. With enough time, money, and enough smart people, could we theoretically optimize this down to the fewest possible machine instructions and the least number of main memory hits? We could. Is that useful? I doubt it. The performance of common password checking is never going to be the thing that makes or sinks your product or application. For this problem, it’s likely that there is a threshold that when hit is “fast enough”, and anything else is unnoticeable by the end user and/or adds code or architectural complexity wildly disproportionate to its benefits.

Getting these passwords into Postgres and queryable by Ecto took about 15 minutes total from my first reading of the post. As I’m already going to be using both in my webapp, I add almost no code and zero dependencies I wasn’t already using. Then, I’ll deploy and monitor. Then, optimize. I hope this is useful to understanding my approach.