Has anyone already created binaries from the miniLZO source to be used from VB?
I don't have access to a C-Compiler and I'm not that good in creating the interface to be used within in VB6.
Source:
http://www.oberhumer.com/opensource/lzo/
Printable View
Has anyone already created binaries from the miniLZO source to be used from VB?
I don't have access to a C-Compiler and I'm not that good in creating the interface to be used within in VB6.
Source:
http://www.oberhumer.com/opensource/lzo/
[...]
Great, I will have a look at it!
Very curious how it it performs compared to Zlib.
If the compression rate for my data is close to this of ZLib and decompression speed is indeed twice as good then it's very promising.
Here's a comparison for that (using the 3 RC5-built-in compression-schemes):Quote:
Originally Posted by Arnoutdv
The compressor which is comparable to LZO is FastLZ (slightly slower in compression,
but also slightly faster in decompression): http://fastlz.org/
I've tested with Bible12.txt (about 5MB, downloadable here: https://www.gutenberg.org/files/30/old/
which should be placed in the App.Path of the VB-Project, which contains the following Form-Code
(also in the App.Path should be the minilzo.dll for the example to work)
Output then (for those who don't want to run it themselves):Code:Option Explicit 'needs a reference to vbRichClient5
Private Declare Function FreeLibrary Lib "kernel32" (ByVal hLibModule As Long) As Long
Private Declare Function LoadLibrary Lib "kernel32" Alias "LoadLibraryA" (ByVal lpLibFileName As String) As Long
Enum eMsg
em_version = 0
em_lastErr = 1
End Enum
Private Declare Function Compress Lib "minilzo.dll" (ByVal bufIn As Long, ByVal inSz As Long, ByVal bufOut As Long, ByVal outSz As Long) As Long
Private Declare Function DeCompress Lib "minilzo.dll" (ByVal bufIn As Long, ByVal inSz As Long, ByVal bufOut As Long, ByVal outSz As Long) As Long
Private Declare Function LZOGetMsg Lib "minilzo.dll" (ByVal Buf As String, ByVal sz As Long, Optional ByVal msgid As eMsg = em_version) As Long
Private hLib As Long
Private Sub Form_Load()
hLib = LoadLibrary(App.Path & "\minilzo.dll")
End Sub
Private Sub Form_Click()
FontName = "Arial": FontSize = 10
AutoRedraw = True: Cls
Dim Crypt As cCrypt
Set Crypt = New_c.Crypt 'instantiate the RC5-Crypt- and Compression-helper
Dim B() As Byte, BCmp() As Byte, BDec() As Byte, i As Long, sC As String
B = New_c.FSO.ReadByteContent(App.Path & "\bible12.txt")
For i = 0 To 3
New_c.Timing True
Select Case i
Case 0: sC = "LZO": LZO B, BCmp
Case 1: sC = "FastLZ": Crypt.FastLZCompress B, BCmp
Case 2: sC = "ZLib": Crypt.ZlibCompress B, BCmp
Case 3: sC = "LZMA": Crypt.LZMAComp B, BCmp, 6
End Select
Print sC; " ", Format(UBound(BCmp) / UBound(B), "Percent"); " "; New_c.Timing,
New_c.Timing True
Select Case i
Case 0: LZO BCmp, BDec, UBound(B) + 1
Case 1: Crypt.FastLZDecompress BCmp, BDec
Case 2: Crypt.ZLibDecompress BCmp, BDec
Case 3: Crypt.LZMADeComp BCmp, BDec
End Select
Print "DeComp-success: "; StrComp(B, BDec) = 0, New_c.Timing
Erase BCmp
Erase BDec
Next i
End Sub
'for decompression, it would probably be better to pass in the original size to get an idea
'of the buffer size to allocate. in practice I would include a header in comporessed data
'that included original size and original md5
'
'note: passing in orgCompressedSize tells it you want to decompress the data..
Function LZO(Buf() As Byte, bOut() As Byte, Optional orgCompressedSize As Long = 0) As Boolean
Dim inSz As Long, sz As Long, outlen As Long
inSz = UBound(Buf) + 1
If orgCompressedSize = 0 Then
outlen = inSz * 2
Else
outlen = orgCompressedSize * 2
End If
ReDim bOut(0 To outlen - 1)
If orgCompressedSize = 0 Then
sz = Compress(VarPtr(Buf(0)), inSz, VarPtr(bOut(0)), outlen)
Else
sz = DeCompress(VarPtr(Buf(0)), inSz, VarPtr(bOut(0)), outlen)
End If
If sz < 1 Then
MsgBox "Compression failed: " & LZOMsg()
Else
ReDim Preserve bOut(0 To sz - 1)
LZO = True
End If
End Function
Function LZOMsg(Optional m As eMsg = em_lastErr)
Dim ver As String
Dim sz As Long
ver = String(500, Chr(0))
sz = LZOGetMsg(ver, Len(ver), m)
If sz > 0 Then
ver = Mid(ver, 1, sz)
LZOMsg = ver
End If
End Function
http://vbRichClient.com/Downloads/Co...Comparison.png
HTH
Olaf
Ouch these results are quite disappointing, especially when the target file was just a text file :(
Quite a big difference in compression rate and just slightly better in decompression speed.
I'm going to do some test on the typical dataset I use.
Arrays of longs which are actually bitvector arrays.
I need to decompress around 2000 of these arrays per calculation day.
Size does matter because my files, which is an archive with about 3000 compressed bitvector arrays, are about 5-7MB per day.
If the files are twice as big then reading the files into memory takes also twice as much time.
These files are typically read from a network share.
So I'm going to do some tests with LZO, but also with FastLZ from vbRichClient.
The results will get closer to what you've probably expected, with increased entropy of theQuote:
Originally Posted by Arnoutdv
input-stream (when the data is less redundant, and/or does follow less predictable patterns) -
e.g. when compressing compiled binaries...
Below is the results when compressing/decompressing the (about 2.5MB) vb_cairo_sqlite.dll:
http://vbRichClient.com/Downloads/Co...omparison2.png
So the differences in compression-ratio are now less between ZLib and the fast compressors -
whilst the decoding-speed got better (relatively, compared to ZLib) - now more than twice
as fast.
From what you wrote about the nature of your Data (BitVectors), I guess you might see
similar tendencies.
Olaf
[...]
I guess it will sit between LZO and ZLib - but googling about the topic some more,Quote:
Originally Posted by dz32
there seems to be a "new star" among the fast compressors:
LZ4 -> http://cyan4973.github.io/lz4/
Also note, that the codecs from Oberhumer (which are all under GPL) -
do not allow commercial distribution along with closed-source-binaries (your App).
Whilst FastLZ (MIT) - and LZ4 (BSD) will allow commercial usage/distrubution.
Olaf
The license for LZO could also be a showstopper.
Thanks for the link to LZ4, have to do some reading on this.
Whether it supports direct memory compression like LZO, Zlib and the compression libraries used in vbRichClient.
@Olaf, your interface to the compression routines used in vbRichClient do store additional information in the compressed byte array, don't they?
And the decompression routines also expect some additional information in the byte array?
Because I currently use zlibwapi.dll and use the "raw" compressed data and I do have my own descriptors in the data to set the decompression buffer size.
Did some tests on my own dataset.
The data consists of 4.217 files (actually arrays), the original size is: 437.5MB
Currently using ZLib compression the compressed archive has a size of 5.9MB
Using LZO the data is compressed to 11.2MB.
The decreased decompression time doesn't make up for additional time needed to read the file.
I also tested QuickLZ and BZip2.
QuickLZ has an even worse compression ratio then LZO.
BZip2 does a better job on the data compression compared to ZLib (5.3MB) but is very slow when decompressing.
So it seems the overall winner for my situation is still ZLib.
I will do an additional test using FastLZ, but the current issue is the additional bytes added by the vbRichClient interface.
Thanks all for your input
If it's for your own use, FreeArc is clearly the best.
Thanks, but It's not for private use and I need a in-memory (de)compression.
If you need zlib compression ratios w/ 3-4x performance increase take a look at the (still unstable) zstd project: https://github.com/Cyan4973/zstd
Edit: Here is a nice compression libraries benchmarks site: https://quixdb.github.io/squash-benchmark/
There I found a small C/C++ library pithy I've never heard before. My VB6 porting effort is WiP but still you can test the stdcall build of the library from `bin/debug_pithy.dll`.
From sample project in `test` directory I get not bad compression ratio for max compression level of 9 and blazing decompression speed on a single core
The input file is a MSSQL database that gets zipped to 443'249 bytes. The compression/decompression speed is for 100 iteration over input file. My CPU is i7-4770 @ 3.50GHz overclocked to 3.9GHzCode:Compression ratio: 17.71% (3'276'800 -> 580'362)
Compression speed: 312.50MB in 903 ms -> 346.07 MB/s
Decompression speed: 312.50MB in 546 ms -> 572.34 MB/s
Here are the results for bible12.txt
And the zip from the link is 1'459'169 bytesCode:Compression ratio: 39.37% (5'213'926 -> 2'052'718)
Compression speed: 497.24MB in 3196 ms -> 155.58 MB/s
Decompression speed: 497.24MB in 1404 ms -> 354.16 MB/s
Here are the results for vb_cairo_sqlite.dll
And the zip is 1'226'299 bytesCode:Compression ratio: 60.28% (2'596'352 -> 1'565'013)
Compression speed: 247.61MB in 1784 ms -> 138.79 MB/s
Decompression speed: 247.61MB in 678 ms -> 365.20 MB/s
The VC2015 optimized build gets another 30% performance increase to 465.58 MB/s decompression speed on bible12.txt but have other issues.
cheers,
</wqw>
Since the new SQLite-version 3.12 was just released, I've used the
occasion to include LZ4 into the __stdcall-compile of vb_cairo_sqlite.dll now.
(Uploaded and available in the new RC5-BaseLib-package -> 5.0.43)...
LZ4 is performing very nicely (especially with regards to decompression-speed,
which is > 1GB/sec) - and so I've also decided to switch over to it in favour
of FastLZ (LZ4 now working behind the scenes of the highlevel-Methods for
cCrypt.FastLZCompress/Decompress - though FastLZDecompress is still capable
to decompress Blobs which were formerly encoded with the FastLZ-algo).
Here's the results for Bible12.txt again:
http://vbRichClient.com/Downloads/Co...omparison4.png
And here those for vb_cairo_sqlite.dll:
http://vbRichClient.com/Downloads/Co...omparison3.png
@wqweto
would be nice if you could test its performance on your fast machine - as said, it
sits behind cCrypt.FastLZ... now (in case you want to use the high-level-API) -
the exposed Flat-APIs are below (if you want to use it more low-level):
The above results were (compression-wise) achieved with LZ4_compress_HC @ CmpLevel 2
(LZ4_HC does additional Block-Analysis to achieve the higher compression at the cost of some
encoding-speed).
The ReturnValues indicate success, when the Results are > 0 - and the "Max-OutBufferSize-Estimate"Code:Declare Function LZ4_compress_default Lib "vb_cairo_sqlite" (bufIn As Any, bufOut As Any, ByVal inSz As Long, ByVal outSz As Long) As Long
Declare Function LZ4_compress_HC Lib "vb_cairo_sqlite" (bufIn As Any, bufOut As Any, ByVal inSz As Long, ByVal outSz As Long, Optional ByVal CmpLevel As Long = 2) As Long
Declare Function LZ4_decompress_safe Lib "vb_cairo_sqlite" (bufIn As Any, bufOut As Any, ByVal inSz As Long, ByVal outSz As Long) As Long
in case of the compression can be safely pre-calculated with (InBufSize * 256/255 + 16).
Olaf
You wrote that you need in-memory compression and decompression. Does that mean you can't use an external exe to compress?
I am curious, since I also would like to find a DLL or lib that I could link to my own programs.
For comparison, FreeArc results on a Core i5:
Code:FreeArc 0.666 creating archive: bib.arc
Compressed 1 file, 5,213,926 => 876,024 bytes. Ratio 16.8%
Compression time: cpu 0.81 secs, real 0.86 secs. Speed 6,077 kB/s
I'd think a lib is more comfortable to use for that (no stdIn/stdOut-piping needed, and no "ShellAndWait").Quote:
Originally Posted by jj2007
FreeArc is not bad (with a good "over-all-profile") - but still not among the "fast compressors"Quote:
Originally Posted by jj2007
which we basically talk about here...
These can be used, to e.g. accomplish a well-performing "In-App-Caching" (which I think
ArnoutDV is after) - so, in a caching-scenario one usually compresses a given ByteArray-Blob once
(compression-speed not all *that* important whilst storing a new Blob) - but then, when multiple repeated
reads are to be performed against the compressed and cached Blob (e.g. sitting in a Hash-Table or Collection),
a superfast Decompression (with nearly no difference to uncompressed Memory-transfers) would be a nice thing to have.
When the compression-ratio is about, say 1/3 - one can cache 3 times as many Blob-Items InMemory,
compared to uncompressed storage - with a still decent "Cache-Read-Performance".
Another scenario which makes the Compression-to-speed-ratio more obvious (and where these
fast compressors make sense) is e.g. "Online-Transfer-Times" from e.g. a Web- or AppServer.
When we e.g. assume, that the "typical Inet-Transfer/Download-speed" is currently at 32MBit/sec on average
(over different Inet-Clients which all have access to the Web- or AppServer) - then let's simplify and say,
that the server will transfer e.g. ResultSets from DB-Selects at roughly 4MByte/sec back to the Clients.
Now let's do some math (assuming a concrete Resultset with an uncompressed size of 1MB) -
and with our assumed average Inet-Transfer-speed of ~4MByte/sec the 1MB would need:
- 0.25sec to reach (and be directly available) to a given Client when transferred uncompressed
Now with an assumed ~100MByte/sec compress-speed and ~1GByte/sec decompress-speed in case of LZ4,
we could do compressed transfers of that 1MB-Recordset - and assuming we reach ~40% size-reduction,
the calculation would be:
- time for serverside compression with 100MByte/sec: 0.01sec
- transfertime for the (to 400KB) reduced Resultset: 0.1sec
- time for clientside decompression with 1GByte/sec: 0.001
Total time until the Rs is available at the clientside: 0.111sec
Now the same transfer again, with FreeArc-compression (assuming a reduction to 20%,
with a compression-speed of 6MB/sec - and a decompression-speed of 50MB/sec).
- time for serverside compression with 6MByte/sec: 0.16sec
- transfertime for the (to 200KB) reduced Resultset: 0.05sec
- time for clientside decompression with 50MByte/sec: 0.02
Total time until the Rs is available at the clientside: 0.23sec
So that result is (although timing-wise better than the "raw-transfer") still about
two times slower, compared to the transfer which was accomplished with the faster compressor
(and it would cause a much higher server-load CPU-wise).
So these fast compressors have their use-cases, despite their lower compression-rates.
Olaf
@Olaf: Here are LZ4 results on my CPU
Compared to pithy LZ4 shows clearly faster decompression but traded 2x slower compressor for some (marginal) 2% compression gains.Code:LZ4 Compression Level 1 ratio: 39.92% (5'213'926 -> 2'081'294)
LZ4 Compression speed: 497.24MB in 6548 ms -> 75.94 MB/s
LZ4 Decompression speed: 497.24MB in 851 ms -> 584.30 MB/s
LZ4 Compression Level 2 ratio: 37.30% (5'213'926 -> 1'944'787)
LZ4 Compression speed: 497.24MB in 6541 ms -> 76.02 MB/s
LZ4 Decompression speed: 497.24MB in 851 ms -> 584.30 MB/s
Pithy Compression ratio: 39.37% (5*213*926 -> 2'052'718)
Pithy Compression speed: 497.24MB in 2773 ms -> 179.31 MB/s
Pithy Decompression speed: 497.24MB in 1103 ms -> 450.81 MB/s
Did you compile the dll with /O2 /Ox optimizations? Is this VC6 compiled or newer? I noticed considerable perf gains w/ VC2015 release builds.
@jj2007: For me it's not "clear" that FreeArc is the best. I'm very happy with nanozip performance for my particular payload -- MSSQL database backups.
Most people would consider anything slower than zip performance an overkill on CPU resources. There are lots of very tight but quite slow compression schemes (BWT comes to mind) that are not pratical for GB payloads e.g. I need to compress 300GB backups daily.
Here are some results FreeArc vs nanozip vs plain zip on my CPU
. . . and bible12.zip got down to 1'369'886 bytes -- very close to nz_lzhd result.Code:D:\TEMP>Arc.exe a bible12 bible12.txt
FreeArc 0.666 creating archive: bible12.arc
Compressed 1 file, 5,213,926 => 876,024 bytes. Ratio 16.8%
Compression time: cpu 0.53 secs, real 0.64 secs. Speed 8,184 kB/s
All OK
D:\TEMP>nz a bible12 bible12.txt
NanoZip 0.09 alpha/Win64 (C) 2008-2011 Sami Runsas www.nanozip.net
Intel(R) Core(TM) i7-4770K CPU @ 3.50GHz|24278 MHz|#4+HT|2797/8135 MB
Archive: bible12.nz
Threads: 4, memory: 512 MB, IO-buffers: 4+1 MB
Compressor #0: nz_optimum1 [44 MB]
Compressed 5 213 926 into 802 536 in 0.41s, 12 MB/s
IO-in: 0.00s, 4972 MB/s.
D:\TEMP>nz a -cd -p1 bible12-cd bible12.txt
NanoZip 0.09 alpha/Win64 (C) 2008-2011 Sami Runsas www.nanozip.net
Intel(R) Core(TM) i7-4770K CPU @ 3.50GHz|27212 MHz|#4+HT|2790/8135 MB
Archive: bible12-cd.nz
Threads: 4, memory: 512 MB, IO-buffers: 20+4 MB
Compressor #0: nz_lzhd [13 MB]
Compressed 5 213 926 into 1 324 633 in 0.11s, 45 MB/s
IO-in: 0.00s, 4972 MB/s.
D:\TEMP>d:\utils\ptime "D:\Program Files\7-Zip\7z.exe" a -tzip bible12 bible12.txt | findstr /i time
ptime 1.0 for Win32, Freeware - http://www.pc-tools.net/
Execution time: 0.850 s
I'm running nz_lzhd compressor on 2 cores for any file above 1GB with `nz a -cd -p2 -m2g` for 3-4 times the performance of plain zip (which is single core by nature) and get always (somewhat) better compression at the end. I fiddled several times but couldn't find FreeArc compressor w/ equivalent perf vs compression ratio. Probably it's CPU dependant too.
cheers,
</wqw>
> For me it's not "clear" that FreeArc is the best. I'm very happy with nanozip
Differences are not big. http://compressionratings.com/rating_sum.html and http://www.maximumcompression.com/da...ry_mf.php#data see FreeArc and NanoZip very close. NZ seems to be in a permanent limbo, though.
@Olaf: Thanks for the examples. Indeed, FA+NZ serve a different purpose.
The results on typically single day dataset, I didn't test the decompression speed yet, only the size of the created archive.
All arrays in the archive consists of 840038 elements, being either Bits, Bytes, Integers, Longs, Singles or Doubles
The bits are actually stored in Longs (32 bits in a Long)
Currently the dataset is compressed using ZLib (zlibwapi 1.2.5) using compression level 9.
Which is the second column in both rows [Zlib (CL=9)]
Decompressing all arrays just once takes an average of 468ms on my computer.Code:Library Uncompressed Zlib (CL=9) LZO 2,09 FastLZ LZMA 9 LZMA 4 QuickLZ BZip2
4217 arrays 458,779,436 6,232,353 11,746,874 11,032,075 5,421,074 5,969,993 14,536,131 5,465,663
437.5MB 5.9MB 11.2MB 10.5MB 5.2MB 5.7MB 13.9MB 5.2MB
Index ZLib 0.0% +88.5% +77.0% -13.0% -4.2% +133.2% -12.3%
Library Uncompressed Zlib (CL=9) vbRC zLib LZ4 LZ4 HC9 LZ4 HC16 LZ4 HC4 LZ4 HC2
4217 arrays 458,779,436 6,232,353 6,565,218 9,739,272 8,762,553 8,607,041 9,191,936 9,705,545
437.5MB 5.9MB 6.3MB 9.3MB 8.4MB 8.2MB 8.8MB 9.3MB
Index ZLib 0.0% +5.3% +56.3% +40.6% +38.1% +47.5% +55.7%
Up until now it seems ZLib seems preferable, compression is very good, decompression speed is also okay.
For LZMA, LZ4 and FastLZ I used the vbRichClient interface.
Had some time to compile a VB6 compatible dll from ZSTD library mentioned above. Here are its results compared to Zlib from vbRC5
Better by a slight margin IMO. Probably the compressor is worth it, decompression speed is on par with zlib. Compression level 7 looks most promising replacement for zlib. This lib can use a data dictionary trained on your data but the API is more complicated. It supports streaming mode, useful if you are compressing and sending data down a socket to the client simultaneously.Code:Zlib Compression Level ratio: 28.00% (5'213'926 -> 1'459'907)
Zlib Compression speed: 497.24MB in 28998 ms -> 17.15 MB/s
Zlib Decompression speed: 497.24MB in 2089 ms -> 238.03 MB/s
ZSTD Compression Level 1 ratio: 30.96% (5'213'926 -> 1'614'265)
ZSTD Compression speed: 497.24MB in 3989 ms -> 124.65 MB/s
ZSTD Decompression speed: 497.24MB in 1950 ms -> 254.99 MB/s
ZSTD Compression Level 5 ratio: 27.74% (5'213'926 -> 1'446'149)
ZSTD Compression speed: 497.24MB in 8590 ms -> 57.89 MB/s
ZSTD Decompression speed: 497.24MB in 2254 ms -> 220.60 MB/s
ZSTD Compression Level 7 ratio: 25.79% (5'213'926 -> 1'344'691)
ZSTD Compression speed: 497.24MB in 14535 ms -> 34.21 MB/s
ZSTD Decompression speed: 497.24MB in 1899 ms -> 261.84 MB/s
ZSTD Compression Level 10 ratio: 24.70% (5'213'926 -> 1'288'097)
ZSTD Compression speed: 497.24MB in 30686 ms -> 16.20 MB/s
ZSTD Decompression speed: 497.24MB in 1783 ms -> 278.88 MB/s
ZSTD Compression Level 14 ratio: 24.13% (5'213'926 -> 1'258'209)
ZSTD Compression speed: 497.24MB in 82613 ms -> 6.02 MB/s
ZSTD Decompression speed: 497.24MB in 1776 ms -> 279.98 MB/s
Here is the basic helper VB6 module I'm using in the tests
cheers,Code:Option Explicit
Private Declare Function LoadLibrary Lib "kernel32" Alias "LoadLibraryA" (ByVal lpLibFileName As String) As Long
Private Declare Function ZSTD_compress Lib "debug_zstd" (dst As Any, ByVal maxDstSize As Long, src As Any, ByVal srcSize As Long, ByVal CompressionLevel As Long) As Long
Private Declare Function ZSTD_decompress Lib "debug_zstd" (dst As Any, ByVal maxDstSize As Long, src As Any, ByVal srcSize As Long) As Long
Public Declare Sub CopyMemory Lib "kernel32" Alias "RtlMoveMemory" (Destination As Any, Source As Any, ByVal Length As Long)
Public Sub ZstdInit()
Call LoadLibrary(App.Path & "\debug_zstd.dll")
End Sub
Public Function ZstdCompress(baSrc() As Byte, baDst() As Byte, Optional ByVal CompressionLevel As Long = 5) As Boolean
Dim lTemp As Long
Dim lSize As Long
lSize = 2 * (UBound(baSrc) + 1) + 4
ReDim baDst(0 To lSize) As Byte
lSize = ZSTD_compress(baDst(4), UBound(baDst) - 3, baSrc(0), UBound(baSrc) + 1, CompressionLevel)
If lSize > 0 Then
lTemp = UBound(baSrc) + 1
Call CopyMemory(baDst(0), lTemp, 4)
ReDim Preserve baDst(0 To lSize + 3)
ZstdCompress = True
End If
End Function
Public Function ZstdDecompress(baSrc() As Byte, baDst() As Byte) As Boolean
Dim lSize As Long
Call CopyMemory(lSize, baSrc(0), 4)
If lSize > 0 Then
ReDim baDst(0 To lSize - 1) As Byte
lSize = ZSTD_decompress(baDst(0), lSize, baSrc(4), UBound(baSrc) - 3)
ZstdDecompress = lSize > 0
End If
End Function
</wqw>
Quite an impressive accumulation of results - thanks for the list...Quote:
Originally Posted by Arnoutdv
When you say, that your daily raw-data consists of 840038 elements,Quote:
Originally Posted by Arnoutdv
do you mean an UDT (or an Array of said UDT) - does it have "SubArrays" in the TypeDef?
The reason I ask is, that you might save quite some space, when the
serialization of the Members of that structure always results in the same
BytePosition for a given Entry within the serialization-stream...
In that case you could try to save e.g. "a whole week" in roughly the same
space - in case there's only slight differences "from day to day".
What I mean is, that you could calculate "the differential" between two
days per XOR - and then compress only the "XORed Result-stream".
Demonstrated with two Longs here, which only change by a simple increment:
Say, the first Long (on Monday) is: 12345678 ... and on the next day ...
(Tuesday) it's just incremented by 1: 12345679
What you currently do is, to compress 12345678 on Monday -
and 12345679 on Tuesday.
What you could consider is, that when you create "weekly archives",
you would only "fully compress" Monday (with the old scheme, similar to
a "Key-Frame" in a Video-stream) - and all the rest of the weekdays
with "XOR-Differentials".
In case of our Example... 12345678 XOR 12345679 = 1 ...
the compressor would see a "nearly empty byte" (the result 1) -
followed by three emtpy Bytes at the given Long-Position in the stream.
.
To restore the Tuesday-Value from Monday and the Differential,
you would only need to apply the XOR again: 12345678 XOR 1 = 12345679
Not sure, whether that is applicable in your scenario - just wanted to
mention the approach...
Olaf
Nice idea, Olaf! I wonder to what extent compressors wouldn't do that automatically. Most of them use a big window to find duplicates, so having seven times a similar dataset should lead to very good ratios. A quick test with FreeArc and 7-Zip:Quote:
Originally Posted by Schmidt
Both could do much better IMHO, maybe there are settings to enlarge the window size. FA took a few seconds, 7z took ages to complete.Code:21.03.97 16:31 4,047,392 bible.txt
25.03.15 00:19 404,739,200 Bible100.txt
31.03.16 05:08 1,113,712 bible.zip
31.03.16 05:10 111,143,060 Bible100.zip
31.03.16 05:08 734,215 bible.arc
31.03.16 05:08 35,658,471 Bible100.arc
Great, thanks! I'm going do so some tests with it.Quote:
Originally Posted by wqweto
I will get back to you
I understand what you mean with this type of Delta Packing.Quote:
Originally Posted by schmidt
But every day is too different compared to the previous day.
The data consists of panel research statements (behavior).
All data is just in a big binary blob.
There are normal data arrays like an array for the panelistIDs and duration of the statement.
Then there are bitvector arrays with a key like "activityid=3", "activityid=8", "location=1", "location=4", "brandid=123", "brandid=4" etc etc
When reading a daily file everything is stored in memory as a big blob, a byte array.
The file also contains a dictionary describing every array in the data:
-key
-offset
-length
-uncompressed_length
-compression_method
-data_type (vbByte, vbInteger ...)
These dictionary items are stored in an UDT array, the key/index pair in a cSortedDictionary.
Then based on the key the index in the UDT is quickly found
These bitvectors are used for pseudo queries like: "(activityid=3&location=1)|(activityid=4&brandid=4)"
The bitvectors combined with "AND" and "OR" relations, returning a new bitvector array.
Then a new function is called to return the set indices from the returned bitvector.
Theses indices are then used to count the panelists and their duration from the base arrays.
A lot my arrays have only sparse values in them, ZLib does stunning compression on this data.
Example:
An array of 840,038 bits, needs 105,008 longs to store the results, but only a few bits are set.
Zlib compresses this array of longs to 130 bytes
ZLib: 130 bytes
LZMA: 94 bytes
LZO: 498 bytes
FastLZ: 439 bytes
LZ4 : 429 bytes
I also have a method which on my data works well for having additional compression.
It's just simply reordering the data in chunks, based on a parameter:
Chunk = 2 -> 1,3,5,7,9... followed by 2,4,6,8,10...
Chunk = 4 -> 1,5,9,13..., 2,6,10,14..., 3,7,11,15..., 4,8,12,16...
This leads often to much better compression, but the downsize is the data has to be re-ordered again after each decompression call.
So at the end I don't use this method for live applications.
Also sometimes using DeltaCompression on the array itself does help, but again this has quite some impact on the performance.
Code:Private Sub ReOrderData(bBytes() As Byte, bReorderOffset As Byte)
Dim lNofBytes As Long
Dim bReorder() As Byte
Dim lCnt As Long, lIndex As Long, l As Long
Dim lReorderOffset As Long
If bReorderOffset < 2 Then Exit Sub
lReorderOffset = bReorderOffset
lNofBytes = UBound(bBytes) + 1
ReDim bReorder(lNofBytes - 1)
lCnt = 0
For lIndex = 0 To lReorderOffset - 1
For l = lIndex To lNofBytes - 1 Step lReorderOffset
bReorder(lCnt) = bBytes(l)
lCnt = lCnt + 1
Next l
Next lIndex
CopyMemory bBytes(0), bReorder(0), lNofBytes
Erase bReorder
End Sub
Public OrderData(bBytes() As Byte, bReorderOffset As Byte)
Dim lNofBytes As Long
Dim bReorder() As Byte
Dim lCnt As Long, lIndex As Long, l As Long
Dim lStepSize As Long, lReorderOffset As Long
If bReorderOffset < 2 Then Exit Sub
lReorderOffset = bReorderOffset
lNofBytes = UBound(bBytes) + 1
ReDim bReorder(lNofBytes - 1)
lStepSize = CLng((lNofBytes) / lReorderOffset + 0.5)
For l = 0 To bReorderOffset - 1
For lIndex = 0 To lStepSize - 1
If (l + lIndex * lReorderOffset) < lNofBytes Then
bReorder(l + lIndex * lReorderOffset) = bBytes(lCnt)
lCnt = lCnt + 1
End If
Next lIndex
Next l
CopyMemory bBytes(0), bReorder(0), lNofBytes
Erase bReorder
End Sub
Private Sub DeltaEncode(bBytes() As Byte)
Dim i As Long
Dim btDelta As Byte, btOriginal As Byte
Dim iBuffer As Integer
btDelta = 0
For i = 0 To UBound(bBytes)
btOriginal = bBytes(i)
iBuffer = CInt(btOriginal) - btDelta
If iBuffer < 0 Then iBuffer = iBuffer + 256
bBytes(i) = iBuffer
btDelta = btOriginal
Next i
End Sub
Private Sub DeltaDecode(bBytes() As Byte)
Dim i As Long
Dim btDelta As Byte
Dim iBuffer As Integer
btDelta = 0
For i = 0 To UBound(bBytes)
iBuffer = CInt(bBytes(i)) + btDelta
If iBuffer > 255 Then iBuffer = iBuffer - 256
bBytes(i) = iBuffer
btDelta = iBuffer
Next i
End Sub
There's "Sparse-Matrix"-approaches, to hold such data efficiently InMemoryQuote:
Originally Posted by Arnoutdv
(no need for "blown-up, normal Arrays" in such cases).
And that hints at, that (along to the way you stored your Data) - you mightQuote:
Originally Posted by Arnoutdv
have destroyed 'context' (Values which better be kept tightly together in a
sequence were moved "out of location").
On a more general note...
I don't have experience with "panel-research" - but I could imagine that
the "true raw data" which daily comes in from a kind of "survey-program",
might be much less "voluminous" than your current ~450MB.
With "true raw data" I mean that this data should not contain anything which
was derived by some math - or AND/OR-combined extra-queries - not sure
how much (or if at all) of such "artificially generated" data is currently contained
in your (uncompressed) daily 450MB.
Isn't there a simple (2D-DataTable-like) scheme behind such surveys -
with simple "Field-Header-Columns" like:
RespondentID, ActivityID, LocationID, BrandID, SatisfactionID, etc.
I mean, there's only so much "raw-data" a willing respondent (who's part of a panel),
is willing to provide in a daily fashion (the above table perhaps not having more
than 20 Columns or so).
Then the amount of daily raw-data (the Rows in above table) is only dependent
on the count of the respondents...
Simply cannot imagine, that this Raw-Table amounts to a daily volume of
450MB (uncompressed).
So my suspicion is, that you're trying to precalculate kind of like an
"OLAP-cube", based on a "Star-Schema" or something - to be able to
deliver "fast answers in any context" - and that these pre-calculations
are responsible for the 450MB?
Olaf
Hi Olaf,
No it's not pre-generated data.
They are behavior statements.
Like watching TV or, some other dataset, internet behavior
The huge uncompressed dataset comes from all the "index" tables.
For example I could have a single array holding the current ActivityID.
But then I would have to loop through the data when reporting ActivityIDs, to see whether the current ActivityID matches one of the ActivityIDs I want to report.
That's why I have for all ActivityIDs used in the current dataset a BitVector to indicate in which row an Activity is used.
If there are 99 unique ActivitityIDs there would be 99 ActivityID bitvectors arrays.
When dealing with Internet research there can be easily 5000+ ActivityIDs (aka websites).
The number of Respondents vary, around 3000-5000 for TV research and between 50K-90K for internet research.
Instead of BitVectors you can also use index arrays, in which only the used "row numbers" are stored.
This give indeed much less uncompressed data, but doing "AND" "OR" relations on multiple arrays is much slower than doing bit operations on long arrays, which also does the bit operation on 32 rows in a single statement.
I tried it using MergeList routines for (sorted) long arrays.
But the constantly redimming of the output array costs time
I have a MergeList for Union and for Intersection. They are fast, but not as fast as doing bit operations.
But in both cases I would compress the data.
Code:Private Function MergeIntersection(List1() As Long, List2() As Long, lOutput() As Long) As Boolean
Dim l1 As Long, l2 As Long
Dim lU1 As Long, lU2 As Long
Dim lValue1 As Long, lValue2 As Long
Dim lCnt As Long
' If 1 of the arrays is empty then the output is also empty
If Not IsDimmed(List1) Then
Erase lOutput
Exit Function
End If
If Not IsDimmed(List2) Then
Erase lOutput
Exit Function
End If
lU1 = UBound(List1)
lU2 = UBound(List2)
ReDim lOutput(lU1)
Do
lValue1 = List1(l1)
lValue2 = List2(l2)
If lValue1 = lValue2 Then
lOutput(lCnt) = lValue1
lCnt = lCnt + 1
l1 = l1 + 1
l2 = l2 + 1
ElseIf lValue1 > lValue2 Then
l2 = l2 + 1
Else
l1 = l1 + 1
End If
Loop Until l1 > lU1 Or l2 > lU2
If lCnt = 0 Then
Erase lOutput
Else
ReDim Preserve lOutput(lCnt - 1)
MergeIntersection = True
End If
End Function
Private Function MergeUnion(List1() As Long, List2() As Long, lOutput() As Long) As Boolean
Dim l1 As Long, l2 As Long
Dim lU1 As Long, lU2 As Long
Dim lValue1 As Long, lValue2 As Long
Dim lCnt As Long, i As Long
Dim bDimmed1 As Boolean, bDimmed2 As Boolean
bDimmed1 = IsDimmed(List1)
bDimmed2 = IsDimmed(List2)
' If both arrays are empty then the result is also empty
If Not bDimmed1 And Not bDimmed2 Then
Erase lOutput
Exit Function
End If
If Not bDimmed1 Then
lOutput = List2
MergeUnion = True
Exit Function
End If
If Not bDimmed2 Then
lOutput = List1
MergeUnion = True
Exit Function
End If
lU1 = UBound(List1)
lU2 = UBound(List2)
ReDim lOutput(lU1 + lU2 + 1)
lValue1 = List1(l1)
lValue2 = List2(l2)
Do
If l1 > lU1 Then
For i = l2 To lU2
lValue2 = List2(i)
If lValue2 <> lValue1 Then
lOutput(lCnt) = lValue2
lCnt = lCnt + 1
End If
Next i
Exit Do
ElseIf l2 > lU2 Then
For i = l1 To lU1
lValue1 = List1(i)
If lValue1 <> lValue2 Then
lOutput(lCnt) = lValue1
lCnt = lCnt + 1
End If
Next i
Exit Do
Else
If lValue1 = lValue2 Then
lOutput(lCnt) = lValue1
l1 = l1 + 1
l2 = l2 + 1
If l1 <= lU1 Then lValue1 = List1(l1)
If l2 <= lU2 Then lValue2 = List2(l2)
ElseIf lValue1 > lValue2 Then
lOutput(lCnt) = lValue2
l2 = l2 + 1
If l2 <= lU2 Then lValue2 = List2(l2)
Else
lOutput(lCnt) = lValue1
l1 = l1 + 1
If l1 <= lU1 Then lValue1 = List1(l1)
End If
lCnt = lCnt + 1
End If
Loop Until l1 > lU1 And l2 > lU2
If lCnt = 0 Then
Erase lOutput
Else
ReDim Preserve lOutput(lCnt - 1)
MergeUnion = True
End If
End Function
Code:' Code for dealing with BitVectors:
Public Sub VectorAND(bv1() As Long, bv2() As Long)
' Bitwise ANDs bv1 and bv2 together, and stores the result in bv1
Dim indx As Long
indx = UBound(bv1) + 1
Do Until indx = 0
indx = indx - 1
bv1(indx) = bv1(indx) And bv2(indx)
Loop
End Sub
Public Sub VectorOR(bv1() As Long, bv2() As Long)
' Bitwise ORs bv1 and bv2 together, and stores the result in bv1
Dim indx As Long
indx = UBound(bv1) + 1
Do While indx <> 0
indx = indx - 1
bv1(indx) = bv1(indx) Or bv2(indx)
Loop
End Sub
Public Sub VectorInvert(bv1() As Long)
' Invert bitvector array and stores the result in bv1
Dim indx As Long
indx = UBound(bv1) + 1
Do While indx <> 0
indx = indx - 1
bv1(indx) = Not bv1(indx)
Loop
End Sub
Public Function GetIndices(BitVector() As Long, lIndices() As Long) As Long
Dim i As Long, ub As Long, lBV As Long
Dim indx As Long, lBit As Long
Dim lCnt As Long
ub = UBound(BitVector)
For indx = 0 To ub
lBV = BitVector(indx)
If lBV Then
i = indx * 32&
For lBit = 0 To 31
If lBV And m_Bits(lBit) Then
lIndices(lCnt) = i + lBit
lCnt = lCnt + 1
End If
Next
End If
Next indx
GetIndices = lCnt
End Function
Public Function IsDimmed(myArray As Variant) As Boolean
On Error GoTo errHandler
IsDimmed = UBound(myArray) >= LBound(myArray)
errHandler:
' obviously not dimensioned yet...
End Function
That's what I assumed basically...Quote:
Originally Posted by Arnoutdv
So, there's (in addition to the "raw-data behaviour-statements" whichQuote:
Originally Posted by Arnoutdv
come in for a given day from your group of "research-respondents") -
also "artificially generated" Index-Data, which you then try to store as well...
I'm not sure, why you are doing all that indexing "by hand" (using your
own structures) - when there's DB-Engines which can ensure that
quite efficiently (well-optimized, and even InMemory)...
SQLite for example can do all that (including the Indexing) on your Raw-Data -
and it is (in your scenario) quite efficient even when storing your
"ID-Ranges"... (SQLite stores Integer-Data with an adaptive scheme,
which ensures that e.g. in a Column, containing only values from 0 to 99,
only "one Byte per Integer-Value" is used - and so on (dynamically) -
for signed Integers up to 64Bit - only using as many bytes as needed...).
The example below simplifies things quite a bit, but it uses an 'INET'-table
which it fills already with 150,000 "raw-records" - under the following assumptions:
- the Records consist of two fields, which are (in combination) unique over ActID, RespID
- ActID stands for a "visited WebSite" - RespID for the Respondent
- each respondent can have more than one record in the table (for different ActID-WebSite)
- the number of "unique Respondents" among the 150,000 records is limited to 40000
- the number of "unique ActID-WebSites" is limited to 5000
The uncompressed DB for the above scenario does have a final size
(including the Indexing over ActID, RespID) of 1.6MB (ZLib-compressed then ~0.8MB).
It will answer Search-Queries typically after only around 1msec (e.g. finding
all Records with a certain ActID).
Filling in the 150.000 Records of Raw-Data is done (including the Indexing)
at startup in about 330msec.
Here's the example (needs two Buttons: cmdTestPerformance and cmdSave on a Form)
I'd play around with that a bit (maybe adding a few more columns, to better matchCode:Option Explicit
Private Cnn As cConnection
Private Sub Form_Load()
Set Cnn = New_c.Connection(, DBCreateInMemory)
Cnn.Execute "Create Table tInet(ActID Integer, RespID Integer, " & _
"PRIMARY KEY (ActID, RespID) ) Without RowID"
Dim Cmd As cCommand, i As Long
Set Cmd = Cnn.CreateCommand("Insert Into tInet(RespID, ActID) Values(?,?)")
New_c.Timing True
Cnn.BeginTrans
For i = 1 To 150000 '150000 reported site-visits from all the respondents
Cmd.SetInt32 1, Rnd * 40000 'a range of max. 40000 unique resp. (each with multiple Site-visits)
Cmd.SetInt32 2, Rnd * 5000 'a range of max. 5000 different WebSite-IDs
Cmd.Execute
Next
Cnn.CommitTrans
Caption = New_c.Timing
End Sub
Private Sub cmdTestPerformance_Click()
'the way the Primary Key (ActID, RespID) was defined on the table, already ensures speedy queries over ActID
New_c.Timing True
Caption = Cnn.OpenRecordset("Select RespID From tInet Where ActID=2000").RecordCount
Caption = Caption & New_c.Timing
End Sub
Private Sub cmdSave_Click()
Const DBName As String = "c:\temp\InetBehaviour.db3"
Dim B() As Byte
If New_c.FSO.FileExists(DBName) Then New_c.FSO.DeleteFile DBName
Cnn.CopyDatabase DBName
New_c.Crypt.ZlibCompress New_c.FSO.ReadByteContent(DBName), B
Caption = "DB-Size: " & Int(New_c.FSO.FileLen(DBName) / 1024) & "KByte, " & _
"Compressed: " & Int((UBound(B) + 1) / 1024) & "KByte"
End Sub
a concrete set of your Raw-Data - perhaps reducing the amount of records
then from 150,000 to something "more common in daily use"...
Olaf
For the background variables, socio demographics, I do use a SQLite DB.
There are about 30 variables (age, gender, social class, area, etc etc)
And the values per respondent can change in time.
This for selecting the active respondents for creating a reporting group like "age 20-34 male"
For the day by day behavior data I've tried that solution too, but it really grew ridiculously.
With a minor problem, some fields are multivalue.
If the data was stored only on a huge DB server (like Hadoop) then I would put all data in single table and let the DB server do all the work, because most analysis require to process at least 1 month of data.
But this is a local PC solution, where data is sent to clients on daily basis.
I'll contact you privately if you don't mind about the performance and the size of a daily SQLite DB.
The data is quite sensitive.
I can imagine that - but would like to find an efficient solution too ...Quote:
Originally Posted by Arnoutdv
(your problem is quite interesting, you can also E-Mail me directly if you like).
Olaf
Additional results using ZSTD:
These compression rates are quite on par with ZLib, now I have to compare the actual decompression speed on my dataset compared to ZLib.Code:Library Uncompressed Zlib (CL=9) ZSTD CL=1 ZSTD CL=5 ZSTD CL=10 ZSTD CL=14
4217 arrays 458,779,436 6,232,353 6,533,262 6,403,100 5,945,740 6,002,778
437.5MB 5.9MB 6.2MB 6.1MB 5.7MB 5.7MB
Index ZLib 0.0% 4,8% 2,7% -4,6% -3,7%
Thanks wqweto for sharing your ZSTD library!
So it look like ZSTD CL=1 is on par with zlib default CL (from vbRC) as compressed size but probably is 10x faster on compression in 2x on decompression.
Btw, the link above is a static build w/ VS2015 so it might not work anything less than Vista as it puts `Subsystem Version: 6.0` in PE header. VC6 builds use 4.0 for subsystem and work on NT4 and above.
I've sent the github project a pull request for stdcall builds w/ MSVC to become part of the project if they accept it, so it can be built w/ VC6 too.
Btw, now I notice that ZSTD is from the author of LZ4 and it seems like ZSTD CL=1 is like a next step in speed/size, a continuation from LZ4 CL=max.
cheers,
</wqw>
VS 2015 will build XP-compatible DLLs if the Project Properties > General > Platform Toolset is set to Windows XP (v140_xp). I believe this option became available with a recent patch?? (Can't remember details, sorry - it's been awhile!)Quote:
Originally Posted by wqweto
Edit: XP support is discussed in this MSDN blog from July. Looks like you may need to reinstall the optional XP targeting features if you installed VS 2015 prior to that point.
Adding /subsystem:windows,5.1 to linker options did the trick. Obviously 6.0 is just a default value for /subsystem option in VS2015 but not the minimum supported.
Thanks for the hint.
cheers,
</wqw>
Just read an update about Zstandard an improved compression method by the developers of Facebook.
Compression very scaleable between speed and size, decompression is extremely fast.
https://code.facebook.com/posts/1658...ith-zstandard/
I did some small tests with command-line tool and the results are very promising!
https://github.com/facebook/zstd/releases
The only resource I could find for VB6 is still the same as already compiled and posted by wqweto in post #20 of this thread.
https://github.com/facebook/zstd/pull/166
My PR for stdcall binding was dismissed as too disruptive as at that time they were making some large changes to the core of the library.
Doubt this PR can be rebased on 1.0 release as is because public interface has been changed a lot and my incentive to revise it is not very high provided it got previously rejected as not very useful.
cheers,
</wqw>
I read through it, quite disappointing :(
https://github.com/wqweto/zstd/releases
Here is a rebuild of the original stdcall modifications on current v1.0 thrunk.
Binaries compiled with VS2015 with `Operating System Version: 5.1` targeting Win XP and above.
Enjoy!
</wqw>
I will check it out!
Compression ratio is better than ZLib when I use compressionlevel>15 for my datasets.
Decompression speed of ZSTD is about 15% better compared to ZLib.
Some more tests in the pipeline.
Conclusion ZSTD compression is great.
Overall compression ratios are better compared to ZLib even better then BZIP2
Decompression speed is even better than Zlib.
No need for LZO, compression ratio is not on par with ZLib, decompression speed gain is not worth it.
Thanks wqweto!