The original page for SSDEEP can be found at http://ssdeep.sourceforge.net/
On that page you find also the binaries for Windows.
Have fun.
SSDEEP in Java
The original page for SSDEEP can be found at http://ssdeep.sourceforge.net/
On that page you find also the binaries for Windows.
Have fun.
Preserving the soul of an old laptop
If you're like me and keep old laptops around the house that are wannabe time-capsules, I've recently started converting the physical operating systems onto virtual machines that I can run from a PC emulator.
The concept is called P2V (Physical To Virtual) and has been made simpler over recent years. My favorite tool for this purpose is provided by VMWare at http://www.vmware.com/products/converter
It is a freeware tool, albeit you have to provide an email address to access the download page. What I like about the tool is the fact that the most difficult steps are automated. All one needs to do is installing, convert and run the new virtual machine through a wizard-driven menu with a few clicks.
Being a VMWare tool you'd think that it restricts running the virtual image to their line of products. However, I was able to use VirtualBox to run and see my old Windows 7 booting and running from a virtual machine.
Very nice, to be able of preserving the old look & feel, the apps, documents and working environment in such a quick manner as hardware moves forward.
The concept is called P2V (Physical To Virtual) and has been made simpler over recent years. My favorite tool for this purpose is provided by VMWare at http://www.vmware.com/products/converter
It is a freeware tool, albeit you have to provide an email address to access the download page. What I like about the tool is the fact that the most difficult steps are automated. All one needs to do is installing, convert and run the new virtual machine through a wizard-driven menu with a few clicks.
Being a VMWare tool you'd think that it restricts running the virtual image to their line of products. However, I was able to use VirtualBox to run and see my old Windows 7 booting and running from a virtual machine.
Very nice, to be able of preserving the old look & feel, the apps, documents and working environment in such a quick manner as hardware moves forward.
Windows: Driver for logging the timing of drivers and services at startup
Sometimes it is good to measure how long a laptop with Windows will take to boot and which drivers or services might be hogging down the boot process. There exist some ways of measuring the time using Microsoft-provided tooling but they aren't redistributable.
To overcome this limitation, I've wrote a simple driver that will write a text file with a time stamp when each other driver or service gets called. This way we can (more or less) expose which drivers or services are taking longer to be loaded.
This is a sample of what to expect:
The code is available under the EUPL terms and hosted on GitHub at this location: https://github.com/nunobrito/BootLogger
On the download folder you find the compiled drivers (x86 and x64 versions) along with the instructions on how to use the driver on your machine.
Feedback from other users can be read at reboot on this topic:
http://reboot.pro/topic/20345-driver-for-logging-windows-boot-drivers-and-services/
Each boot log report will be placed under c:\BootLogger, this parameter is configurable in case you want to change it.
Have fun!
:-)
To overcome this limitation, I've wrote a simple driver that will write a text file with a time stamp when each other driver or service gets called. This way we can (more or less) expose which drivers or services are taking longer to be loaded.
This is a sample of what to expect:
18/02/2015 13:16:40.437, Driver, 4, \SystemRoot\System32\Drivers\crashdmp.sys
18/02/2015 13:16:40.453, Driver, 4, \SystemRoot\System32\Drivers\iaStor.sys
18/02/2015 13:16:40.453, Driver, 4, \SystemRoot\System32\Drivers\dumpfve.sys
18/02/2015 13:16:40.812, Driver, 4, \SystemRoot\system32\DRIVERS\cdrom.sys
18/02/2015 13:16:40.812, Driver, 4, \SystemRoot\System32\Drivers\Null.SYS
18/02/2015 13:16:40.828, Driver, 4, \SystemRoot\System32\Drivers\Beep.SYS
18/02/2015 13:16:40.843, Driver, 4, \SystemRoot\System32\drivers\watchdog.sys
18/02/2015 13:16:40.843, Driver, 4, \SystemRoot\System32\drivers\VIDEOPRT.SYS
18/02/2015 13:16:40.843, Driver, 4, \SystemRoot\System32\drivers\vga.sys
18/02/2015 13:16:40.843, Driver, 4, \SystemRoot\System32\DRIVERS\RDPCDD.sys
18/02/2015 13:16:40.859, Driver, 4, \SystemRoot\system32\drivers\rdpencdd.sys
18/02/2015 13:16:40.859, Driver, 4, \SystemRoot\system32\drivers\rdprefmp.sys
18/02/2015 13:16:40.859, Driver, 4, \SystemRoot\System32\Drivers\Msfs.SYS
18/02/2015 13:16:40.875, Driver, 4, \SystemRoot\System32\Drivers\Npfs.SYS
18/02/2015 13:16:40.875, Driver, 4, \SystemRoot\system32\DRIVERS\TDI.SYS
The code is available under the EUPL terms and hosted on GitHub at this location: https://github.com/nunobrito/BootLogger
On the download folder you find the compiled drivers (x86 and x64 versions) along with the instructions on how to use the driver on your machine.
Feedback from other users can be read at reboot on this topic:
http://reboot.pro/topic/20345-driver-for-logging-windows-boot-drivers-and-services/
Each boot log report will be placed under c:\BootLogger, this parameter is configurable in case you want to change it.
Have fun!
:-)
Olhando à frente
Olhando à frente
existe rumo diferente.
Rumo que dita o futuro,
de curto tempo e alento
para escapar o tormento
que traz o curto momento.
Assim temos um ano
pouco sano e profano
que de tal visto amanho
só pode trazer mais dano.
Serão dez meses a terminar
esta pequena obra d'encantar,
que deu tanto gosto de começar,
e tão pouco tempo para saborear
Imagino como seria o dia
em que o peso desaparecia.
Um dia correndo de alegria,
iria apreciar, seria magia
Tal dia chegará
um dia, oxalá.
existe rumo diferente.
Rumo que dita o futuro,
de curto tempo e alento
para escapar o tormento
que traz o curto momento.
Assim temos um ano
pouco sano e profano
que de tal visto amanho
só pode trazer mais dano.
Serão dez meses a terminar
esta pequena obra d'encantar,
que deu tanto gosto de começar,
e tão pouco tempo para saborear
Imagino como seria o dia
em que o peso desaparecia.
Um dia correndo de alegria,
iria apreciar, seria magia
Tal dia chegará
um dia, oxalá.
Java hidden gem: CopyOnWriteArrayList()
CopyOnWriteArrayList() is a cousin of the well-known ArrayList() class.
ArrayList is often used for storing items. On my case, I had been working on a multi-threaded program that shared a common ArrayList.
In order to improve performance, every now and then I would like to remove some of the items on this list when matched some criteria. In the past I would use the Iterator() class to iterate through item using the iterator.next() function.
To remove an item I'd just call iterator.delete(). However, this approach was failing for some odd reason:
So, what else can one try? Looking around the web I've found the not-so-known CopyOnWriteArrayList() and to my surprise solved the problem with a nice performance boost.
Works in the same manner as a typical Arraylist but doesn't synchronize the items when they are removed. To remove items I use a second Arraylist that is decoupled and place the items to remove there. Then, an independent status thread is running in interval loops of three seconds to check if this second Arraylist has any items, removing them from the main list in asynchronous manner.
All in all, running the code in multi-threaded mode and adopting CopyOnArrayWriteArrayList() reduced the overall processing time for 17 million lines of data from 30 minutes to around 10 minutes, an average of 30k lines/second. The text database used as example is sized in 12,3 Gb and contains 2.5 billion snippets that are compared against 164 methods of my test sample.
This translates to roughly 41 billion comparisons taking place in 10 minutes.
As reference, when my computer is just reading the lines without any processing then it reaches an average speed of 140k lines/second, this value reveals the upper I/O limit expected as disk bandwidth. The speed of 30k lines/second occurs (probably) due to CPU limitations (an i7 core) when doing similarity comparisons between strings.
The performance is not bad, but at this point I'm running out of ideas on how to further bring down the processing time. The bottleneck is still the comparison algorithm, I've already wrote a cheaper/dirty version of Levensthein's algorithm for faster comparisons but still is not enough.
Any ideas?
EDIT
After some more time looking on performance I've noted that comparison of two strings was being made using String objects. There was redundant transformation back and forth between char[] and String objects. The code was modified to run using only char[] arrays. Speed was doubled, is now averaging 60k lines/second, taking 5 minutes to complete the same processing because less stress is placed on the CPU.
ArrayList is often used for storing items. On my case, I had been working on a multi-threaded program that shared a common ArrayList.
In order to improve performance, every now and then I would like to remove some of the items on this list when matched some criteria. In the past I would use the Iterator() class to iterate through item using the iterator.next() function.
To remove an item I'd just call iterator.delete(). However, this approach was failing for some odd reason:
java.util.ConcurrentModificationException at java.util.AbstractList$Itr.checkForComodification (AbstractList.java:372)I tried to place synchronized on the relevant methods but processing just got slower, not solving the error failure.
So, what else can one try? Looking around the web I've found the not-so-known CopyOnWriteArrayList() and to my surprise solved the problem with a nice performance boost.
Works in the same manner as a typical Arraylist but doesn't synchronize the items when they are removed. To remove items I use a second Arraylist that is decoupled and place the items to remove there. Then, an independent status thread is running in interval loops of three seconds to check if this second Arraylist has any items, removing them from the main list in asynchronous manner.
All in all, running the code in multi-threaded mode and adopting CopyOnArrayWriteArrayList() reduced the overall processing time for 17 million lines of data from 30 minutes to around 10 minutes, an average of 30k lines/second. The text database used as example is sized in 12,3 Gb and contains 2.5 billion snippets that are compared against 164 methods of my test sample.
This translates to roughly 41 billion comparisons taking place in 10 minutes.
As reference, when my computer is just reading the lines without any processing then it reaches an average speed of 140k lines/second, this value reveals the upper I/O limit expected as disk bandwidth. The speed of 30k lines/second occurs (probably) due to CPU limitations (an i7 core) when doing similarity comparisons between strings.
The performance is not bad, but at this point I'm running out of ideas on how to further bring down the processing time. The bottleneck is still the comparison algorithm, I've already wrote a cheaper/dirty version of Levensthein's algorithm for faster comparisons but still is not enough.
Any ideas?
EDIT
After some more time looking on performance I've noted that comparison of two strings was being made using String objects. There was redundant transformation back and forth between char[] and String objects. The code was modified to run using only char[] arrays. Speed was doubled, is now averaging 60k lines/second, taking 5 minutes to complete the same processing because less stress is placed on the CPU.
Java: RandomAccessFile + BufferedReader = FileRandomReadLines
In the Java world when reading large text files you are usually left with two options:
Option 1) allows to read text from any given part of the file but is not buffered, meaning that it will be slow to read lines.
Option 2) is buffered, therefore fast but you need to read each line from the beginning of the text file until you reach where you want to really read data.
There are strategies to cope with these mutually exclusive options, one is to read data sequentially, another option is to partition data into different files. However, sometimes you just have that case where you need to resume some time consuming operation (think on a scale of days) where billions of default sized lines are involved. Neither option 1) nor option 2) will suffice.
Up to this point I was trying to improve performance, remove any IF's and any code that could squeeze a few more ounces of speed but the problem remained the same: we need an option 3) that mixes the best of both options. There wasn't one readily available that I could find around the Internet.
In the meanwhile I have found a hint that might be possible to feed a BufferedReader directly from a RandomAccessFile. Tested this idea and was indeed possible, albeit still with some rough edges.
For example, if we are already reading data from the BufferedReader and decide to change the file position on the RandomAccessFile object, the BufferedReader will get erroneous data on the buffer. The solution that I've applied is to simply re-create a new BufferedReader, forcing the buffer to be reset.
Now, I'm making available the code that combines the these two approaches. You find the RandomAccessFile class at https://github.com/nunobrito/utils/blob/master/Utils/src/utils/ReadWrite/FileRandomReadLines.java
Has no third-party dependencies, you are likely fine by just downloading and including it on your code. Maybe there is already similar implementation elsewhere published before, I didn't found one and tried as much as possible to find some ready-made code.
If you see any improvements possible, do let me know and I'll include your name on the credits.
- RandomAccessFile
- BufferedReader
Option 1) allows to read text from any given part of the file but is not buffered, meaning that it will be slow to read lines.
Option 2) is buffered, therefore fast but you need to read each line from the beginning of the text file until you reach where you want to really read data.
There are strategies to cope with these mutually exclusive options, one is to read data sequentially, another option is to partition data into different files. However, sometimes you just have that case where you need to resume some time consuming operation (think on a scale of days) where billions of default sized lines are involved. Neither option 1) nor option 2) will suffice.
Up to this point I was trying to improve performance, remove any IF's and any code that could squeeze a few more ounces of speed but the problem remained the same: we need an option 3) that mixes the best of both options. There wasn't one readily available that I could find around the Internet.
In the meanwhile I have found a hint that might be possible to feed a BufferedReader directly from a RandomAccessFile. Tested this idea and was indeed possible, albeit still with some rough edges.
For example, if we are already reading data from the BufferedReader and decide to change the file position on the RandomAccessFile object, the BufferedReader will get erroneous data on the buffer. The solution that I've applied is to simply re-create a new BufferedReader, forcing the buffer to be reset.
Now, I'm making available the code that combines the these two approaches. You find the RandomAccessFile class at https://github.com/nunobrito/utils/blob/master/Utils/src/utils/ReadWrite/FileRandomReadLines.java
Has no third-party dependencies, you are likely fine by just downloading and including it on your code. Maybe there is already similar implementation elsewhere published before, I didn't found one and tried as much as possible to find some ready-made code.
If you see any improvements possible, do let me know and I'll include your name on the credits.
A trillion files
2014 has come to an end, so I'm writing a retrospective about what happened and what might be coming down the road in 2015.
For me, the year had the first milestone reached in February with a talk about SPDX and open source in FOSDEM. At that time I was applying to a position as co-chair for the SPDX working group but another candidate in Europe was chosen, apparently more suited.
Nevertheless, I kept throughout the year with my work related to the SPDX open format. In FOSDEM was debuted the first graphical visualizer for SPDX documents, in the process was written a license detection engine to find common software licenses and place this information on newly generated SPDX documents.
On the TripleCheck side, funding was a growing difficulty across the year. After FOSDEM there was urgency in raising funds to keep the company running. At that point we had no MVP (minimum viable prototype) to show and investors had no interest in joining the project. Despite our good intentions and attempts to explain the business concept, we didn't had the needed presentation and business skills to move forward. The alternative option for funding without depending on investors was the EUREKA funding from the EuroStars program.
For this purpose was formed a partnership with an aerospace organization and another company well matured in the open source field. We aimed to move a step forward in terms of open source licensing analysis. After months of preparation, iteration and project submission we got a reply: not accepted. The critique that pained me the most was reading that our project would be open source, therefore unable to maintain a sustainable business because competitors would copy our work. Maybe they have a point, but being open source ourselves is our leverage against competitors since this is a path they will not cross and that opened the doors of the enterprise industry to what we do. Open sourced companies are hard to succeed, despite the hard path I wasn't willing to see us become like the others.
In parallel, people had been hired in previous months to work on the business side of TripleCheck but it just wasn't working as we hoped. The focus then moved strictly to code development and reach an MVP but this wasn't working from a financial perspective either. At this point my own bank savings were depleted, the company reduced back to the two original founding members and seemed the end of the story for yet another startup that tried their luck. We did not had the finances, nor the team, nor the infrastructure to process open source software in large scale.
Failure was here, was time to quit and go home. So, as an engineer I just assumed failure as a consolidated fact. Now with everything failed, there was nothing to lose. The question was "what now?"
There was enough money in the bank to pay rent and stay at home for a couple of months. Finding a new job is relatively easy when you know your way around computers. It was a moment very much like a certain song where the only thing occupying the mind was not really failure, but the fact that I remained passionate about solving the licensing problem and wanted to get this project done.
So, let's clear the mind and start fresh. No outside financing from VC, no ambitious business plans, no business experts, no infrastructure nor any resources other than what is available right now. Let's make things work.
Kept working on the tooling, kept moving forward and eventually got approached by companies that needed consulting. TripleCheck was no longer a startup looking for explosive growth, it had now the modest ambition of making enough to pay the bills and keep working with open source.
Consulting on the field of open source compliance is not easy when you're a small company. While bigger consulting companies on this field can afford to just give back a report listing what is wrong with the code of a client, we had to do the same, plus putting our hands to change the code and make it compliant. Looking back in time, this was one heck of way to get expertise in complete and fast-forward manner.
Each client became a beta-tester for the tooling developed at the same time. This meant that the manual process was incrementally replaced with an automated method. Our tooling got improved with each analysis that brought different code to analyze, different requirements and different licenses to interpret. At the some point the tooling got so accurate that could now detect licensing faults on the open source code from companies such as Microsoft.
At this time surfaced our first investor. A client was selling his company and he got amazed with the work done while inspecting his code. For me this was one of those turning points, now we had a business expert on our side. Our old powerpoint pitch-decks were crap, nobody really understood why someone needed a compliance check. But this investor had lived through the pain of not having his code ready for acquisition and how relevant this code repair had been. This had become an opportunity to bring aboard a person with first hand experience as a client that we didn't had to explain why it mattered to fix licensing with a tool, not an expert human.
With his support more business got done and our presentation improved. Was now possible to move forward. One of the goals in mind was the creation of an independent open source archive. In August we reached the mark of 100 million source code files archived. A new type of technology dubbed "BigZip" was developed for this purpose since normal file systems and archives were ill suited for this scale of archive processing. A good friend of mine described nicely this concept as a "reversed zipped tar". Meaning that we create millions of zip files inside a single file, the reverse action of what tar.gz does in Linux.
This way got solved the problem of processing files in large numbers. To get files from the Internet was developed a project called "gitFinder" that retrieved over 7 million open source projects. Our first significant data-set had been achieved.
In August was time for the first presence with a stand for TripleCheck on a conference, the FrOSCon. At this event we already had developed a new technology that was able to find snippets of code which were not original. It was dubbed "F2F", based on a humour inspired motto: "Hashes to Hashes, FOSS to FOSS" as a mock to the fact that file hashes (MD5, SHA1, ..) were used for exposing FOSS source code files inside proprietary code.
This code created a report indicating the snippets of code that were not original and where else on the Internet they could be found. For this purpose I wrote a token translator/comparator and a few other algorithms to detect code similarity. The best memory that I have from this development happened when writing part of the code on a boat directly in front of the Eiffel tower. When you're a developer, these are the memories that one remembers with a smile as years pass.
Shortly later in October, TripleCheck got attention at LinuxCon in Europe. For this event we brought aboard a partnership with http://searchcode.com to create or view online an SPDX document from a given repository on GitHub. In the same event we made available a DIY project that enabled anyone to generate 1 million SPDX documents. To provide context, the SPDX format is criticized by the lack of example documents available to public. The goal was making available as many documents as possible. Sadly, no public endorsement from the SPDX working group came to this kind of activities. To make matters worse, too often my emails went silently ignored on the mailing list whenever proposing improvements. That was sad, had real hopes to see this open standard rise.
Can only wonder if the Linux Foundation will ever react. I'm disenchanted with the SPDX direction but believe we (community) very much need this open standard for code licensing to exist, so I keep working to make it reachable and free of costs.
From November to December the focus was scaling our infrastructure. This meant a code rewrite to apply lessons learned. The code complexity was simplified to a level where we can keep using inexpensive hardware and software where only 1~2 developers are needed to improve the code.
The result was a platform that reached by the end of December the milestone of one trillion files archived. In this sense we achieved what others said to be impossible without the proper funds. These files belong to several million projects around the web that are now ready for use in future code analysis. For example, upcoming in 2015 is the introduction of two similarity matching algorithms converted to Java. One of them is TLSH from TrendMicro and the second is SDHash. This is code that we are directly donating back to the original authors after conversion and will be testing to see how it performs on code comparisons.
In retrospective I am happy. We passed through great and collapsing moments, lived through a journey that builds code that others can reuse. I'm happy that TripleCheck published more code in a single year than any other licensing compliance provider has ever done over the term of their existence, which in most cases is above a decade.
At the end of day after TripleCheck is long gone, it is this same code that will remain public and reachable for other folks to re-use. Isn't knowledge sharing one of the cornerstones of human revolution? In 2014 we have helped human knowledge about source code to move forward, let's now start 2015.
For me, the year had the first milestone reached in February with a talk about SPDX and open source in FOSDEM. At that time I was applying to a position as co-chair for the SPDX working group but another candidate in Europe was chosen, apparently more suited.
Nevertheless, I kept throughout the year with my work related to the SPDX open format. In FOSDEM was debuted the first graphical visualizer for SPDX documents, in the process was written a license detection engine to find common software licenses and place this information on newly generated SPDX documents.
On the TripleCheck side, funding was a growing difficulty across the year. After FOSDEM there was urgency in raising funds to keep the company running. At that point we had no MVP (minimum viable prototype) to show and investors had no interest in joining the project. Despite our good intentions and attempts to explain the business concept, we didn't had the needed presentation and business skills to move forward. The alternative option for funding without depending on investors was the EUREKA funding from the EuroStars program.
For this purpose was formed a partnership with an aerospace organization and another company well matured in the open source field. We aimed to move a step forward in terms of open source licensing analysis. After months of preparation, iteration and project submission we got a reply: not accepted. The critique that pained me the most was reading that our project would be open source, therefore unable to maintain a sustainable business because competitors would copy our work. Maybe they have a point, but being open source ourselves is our leverage against competitors since this is a path they will not cross and that opened the doors of the enterprise industry to what we do. Open sourced companies are hard to succeed, despite the hard path I wasn't willing to see us become like the others.
In parallel, people had been hired in previous months to work on the business side of TripleCheck but it just wasn't working as we hoped. The focus then moved strictly to code development and reach an MVP but this wasn't working from a financial perspective either. At this point my own bank savings were depleted, the company reduced back to the two original founding members and seemed the end of the story for yet another startup that tried their luck. We did not had the finances, nor the team, nor the infrastructure to process open source software in large scale.
Failure was here, was time to quit and go home. So, as an engineer I just assumed failure as a consolidated fact. Now with everything failed, there was nothing to lose. The question was "what now?"
There was enough money in the bank to pay rent and stay at home for a couple of months. Finding a new job is relatively easy when you know your way around computers. It was a moment very much like a certain song where the only thing occupying the mind was not really failure, but the fact that I remained passionate about solving the licensing problem and wanted to get this project done.
So, let's clear the mind and start fresh. No outside financing from VC, no ambitious business plans, no business experts, no infrastructure nor any resources other than what is available right now. Let's make things work.
Kept working on the tooling, kept moving forward and eventually got approached by companies that needed consulting. TripleCheck was no longer a startup looking for explosive growth, it had now the modest ambition of making enough to pay the bills and keep working with open source.
Consulting on the field of open source compliance is not easy when you're a small company. While bigger consulting companies on this field can afford to just give back a report listing what is wrong with the code of a client, we had to do the same, plus putting our hands to change the code and make it compliant. Looking back in time, this was one heck of way to get expertise in complete and fast-forward manner.
Each client became a beta-tester for the tooling developed at the same time. This meant that the manual process was incrementally replaced with an automated method. Our tooling got improved with each analysis that brought different code to analyze, different requirements and different licenses to interpret. At the some point the tooling got so accurate that could now detect licensing faults on the open source code from companies such as Microsoft.
At this time surfaced our first investor. A client was selling his company and he got amazed with the work done while inspecting his code. For me this was one of those turning points, now we had a business expert on our side. Our old powerpoint pitch-decks were crap, nobody really understood why someone needed a compliance check. But this investor had lived through the pain of not having his code ready for acquisition and how relevant this code repair had been. This had become an opportunity to bring aboard a person with first hand experience as a client that we didn't had to explain why it mattered to fix licensing with a tool, not an expert human.
With his support more business got done and our presentation improved. Was now possible to move forward. One of the goals in mind was the creation of an independent open source archive. In August we reached the mark of 100 million source code files archived. A new type of technology dubbed "BigZip" was developed for this purpose since normal file systems and archives were ill suited for this scale of archive processing. A good friend of mine described nicely this concept as a "reversed zipped tar". Meaning that we create millions of zip files inside a single file, the reverse action of what tar.gz does in Linux.
This way got solved the problem of processing files in large numbers. To get files from the Internet was developed a project called "gitFinder" that retrieved over 7 million open source projects. Our first significant data-set had been achieved.
In August was time for the first presence with a stand for TripleCheck on a conference, the FrOSCon. At this event we already had developed a new technology that was able to find snippets of code which were not original. It was dubbed "F2F", based on a humour inspired motto: "Hashes to Hashes, FOSS to FOSS" as a mock to the fact that file hashes (MD5, SHA1, ..) were used for exposing FOSS source code files inside proprietary code.
This code created a report indicating the snippets of code that were not original and where else on the Internet they could be found. For this purpose I wrote a token translator/comparator and a few other algorithms to detect code similarity. The best memory that I have from this development happened when writing part of the code on a boat directly in front of the Eiffel tower. When you're a developer, these are the memories that one remembers with a smile as years pass.
Shortly later in October, TripleCheck got attention at LinuxCon in Europe. For this event we brought aboard a partnership with http://searchcode.com to create or view online an SPDX document from a given repository on GitHub. In the same event we made available a DIY project that enabled anyone to generate 1 million SPDX documents. To provide context, the SPDX format is criticized by the lack of example documents available to public. The goal was making available as many documents as possible. Sadly, no public endorsement from the SPDX working group came to this kind of activities. To make matters worse, too often my emails went silently ignored on the mailing list whenever proposing improvements. That was sad, had real hopes to see this open standard rise.
Can only wonder if the Linux Foundation will ever react. I'm disenchanted with the SPDX direction but believe we (community) very much need this open standard for code licensing to exist, so I keep working to make it reachable and free of costs.
From November to December the focus was scaling our infrastructure. This meant a code rewrite to apply lessons learned. The code complexity was simplified to a level where we can keep using inexpensive hardware and software where only 1~2 developers are needed to improve the code.
The result was a platform that reached by the end of December the milestone of one trillion files archived. In this sense we achieved what others said to be impossible without the proper funds. These files belong to several million projects around the web that are now ready for use in future code analysis. For example, upcoming in 2015 is the introduction of two similarity matching algorithms converted to Java. One of them is TLSH from TrendMicro and the second is SDHash. This is code that we are directly donating back to the original authors after conversion and will be testing to see how it performs on code comparisons.
In retrospective I am happy. We passed through great and collapsing moments, lived through a journey that builds code that others can reuse. I'm happy that TripleCheck published more code in a single year than any other licensing compliance provider has ever done over the term of their existence, which in most cases is above a decade.
At the end of day after TripleCheck is long gone, it is this same code that will remain public and reachable for other folks to re-use. Isn't knowledge sharing one of the cornerstones of human revolution? In 2014 we have helped human knowledge about source code to move forward, let's now start 2015.
The old new things
You probably wouldn't know this, but I keep an old computer book on my table.
The title is "Análise e programação de computadores", published in 1970 in Portuguese language by Raúl Verde. Should be noted that the first computer book written in my native language had been published only two years earlier, by the same author.
I keep this book on my table because it teaches the basic principles that an aspiring computer programmer should aim to understand. It focuses on the programming of high-level languages such as Cobol and Fortran. Discusses the tradeoffs between using cards to store data vs paper/magnetic tapes or provide formulas to expose the strong points and make informed decisions.
This book could seem awkward if published today, mostly because it mixes software development with engineering, architecture and business interests that have grown specialized. Yet, these principles remain the same and should row on the same direction. Albeit technology grew and matured, truth is that we keep working to push into new boundaries, squeezing performance out of what is now reachable and to somehow make things work.
In this sense, I find it curious how much of the software I'm developing today is holding a strong resemblance with the old techniques on the book. The usage of flat-files, the console output that helps to monitor results, the considerations about storage and its impact on speed/capacity/costs.
Paraphrasing a blog title, I'm reminded that humans do old new things.
This month I had the task of downloading over a billion files from the Internet on a single run. Compare the writing on this book with the current tasks today, they are not different. Even the term "scale" is no excuse when we place these challenges into context.
And yet, as I look to a thousand lines per minute scrolling through that silent terminal, this gives me a pause of happiness. Data is getting processed, things are working, the system is fast enough.
Each line on this screen represents a repository of code and files for a given person. What kind of work or history was that person developing? Then I think on the millions of other repositories still left to process, this is something pretty to just watch as it scrolls.
In some weird kind of sense for a computer geek, looking at these lines on a terminal feels for me as looking at the stars at night. Imagining how each bright dot is around its own sun, planets and history.
Would these two things be comparable? Perhaps yes, perhaps not.
The old new thing is something to think about.
The title is "Análise e programação de computadores", published in 1970 in Portuguese language by Raúl Verde. Should be noted that the first computer book written in my native language had been published only two years earlier, by the same author.
I keep this book on my table because it teaches the basic principles that an aspiring computer programmer should aim to understand. It focuses on the programming of high-level languages such as Cobol and Fortran. Discusses the tradeoffs between using cards to store data vs paper/magnetic tapes or provide formulas to expose the strong points and make informed decisions.
This book could seem awkward if published today, mostly because it mixes software development with engineering, architecture and business interests that have grown specialized. Yet, these principles remain the same and should row on the same direction. Albeit technology grew and matured, truth is that we keep working to push into new boundaries, squeezing performance out of what is now reachable and to somehow make things work.
In this sense, I find it curious how much of the software I'm developing today is holding a strong resemblance with the old techniques on the book. The usage of flat-files, the console output that helps to monitor results, the considerations about storage and its impact on speed/capacity/costs.
Paraphrasing a blog title, I'm reminded that humans do old new things.
This month I had the task of downloading over a billion files from the Internet on a single run. Compare the writing on this book with the current tasks today, they are not different. Even the term "scale" is no excuse when we place these challenges into context.
And yet, as I look to a thousand lines per minute scrolling through that silent terminal, this gives me a pause of happiness. Data is getting processed, things are working, the system is fast enough.
Each line on this screen represents a repository of code and files for a given person. What kind of work or history was that person developing? Then I think on the millions of other repositories still left to process, this is something pretty to just watch as it scrolls.In some weird kind of sense for a computer geek, looking at these lines on a terminal feels for me as looking at the stars at night. Imagining how each bright dot is around its own sun, planets and history.
Would these two things be comparable? Perhaps yes, perhaps not.
The old new thing is something to think about.
Java: Reading the last line on a large text file
Following the recent batch of posts related to text files, sometimes is necessary to retrieve the last line on a given text file.
My traditional way of doing this operation is to use the buffered reader and iterate all lines until the last one is reached. This works relatively fast, at around 400k lines per second on a typical i7 CPU (4 cores) at 2.4Ghz in 2014.
However, for text files with hundreds of million lines this approach grows increasingly too slow.
One solution is using RandomAccessFile to access any point of the file without delay. Since we don't know the exact position of the last line, a possible solution is to iterate each of the last characters until the break line is found.
Seeking one position at a time and just reading a single char might not be the most efficient approach. So, reading a buffer with 1000 characters at a time is a possible improvement on a future implementation.
Nevertheless, the code snippet below solves my issue and gets the last line on a large text file under a millisecond, regardless of the number of lines on the file.
If you're worried about re-using this method. Might help to assure that I've authored this code snippet and that you are welcome to reuse this code under the MIT license terms. You are welcome to improve the code, there is certainly room for optimization.
Hope this helps.
:-)
My traditional way of doing this operation is to use the buffered reader and iterate all lines until the last one is reached. This works relatively fast, at around 400k lines per second on a typical i7 CPU (4 cores) at 2.4Ghz in 2014.
However, for text files with hundreds of million lines this approach grows increasingly too slow.
One solution is using RandomAccessFile to access any point of the file without delay. Since we don't know the exact position of the last line, a possible solution is to iterate each of the last characters until the break line is found.
Seeking one position at a time and just reading a single char might not be the most efficient approach. So, reading a buffer with 1000 characters at a time is a possible improvement on a future implementation.
Nevertheless, the code snippet below solves my issue and gets the last line on a large text file under a millisecond, regardless of the number of lines on the file.
/** * Returns the last line from a given text file. This method is particularly * well suited for very large text files that contain millions of text lines * since it will just seek the end of the text file and seek the last line * indicator. Please use only for large sized text files. * * @param file A file on disk * @return The last line or an empty string if nothing was found * * @author Nuno Brito * @author Michael Schierl * @license MIT * @date 2014-11-01 */ public static String getLastLineFast(final File file) { // file needs to exist if (file.exists() == false || file.isDirectory()) { return ""; } // avoid empty files if (file.length() <= 2) { return ""; } // open the file for read-only mode try { RandomAccessFile fileAccess = new RandomAccessFile(file, "r"); char breakLine = '\n'; // offset of the current filesystem block - start with the last one long blockStart = (file.length() - 1) / 4096 * 4096; // hold the current block byte[] currentBlock = new byte[(int) (file.length() - blockStart)]; // later (previously read) blocks List<byte[]> laterBlocks = new ArrayList<byte[]>(); while (blockStart >= 0) { fileAccess.seek(blockStart); fileAccess.readFully(currentBlock); // ignore the last 2 bytes of the block if it is the first one int lengthToScan = currentBlock.length - (laterBlocks.isEmpty() ? 2 : 0); for (int i = lengthToScan - 1; i >= 0; i--) { if (currentBlock[i] == breakLine) { // we found our end of line! StringBuilder result = new StringBuilder(); // RandomAccessFile#readLine uses ISO-8859-1, therefore // we do here too result.append(new String(currentBlock, i + 1, currentBlock.length - (i + 1), "ISO-8859-1")); for (byte[] laterBlock : laterBlocks) { result.append(new String(laterBlock, "ISO-8859-1")); } // maybe we had a newline at end of file? Strip it. if (result.charAt(result.length() - 1) == breakLine) { // newline can be \r\n or \n, so check which one to strip int newlineLength = result.charAt(result.length() - 2) == '\r' ? 2 : 1; result.setLength(result.length() - newlineLength); } return result.toString(); } } // no end of line found - we need to read more laterBlocks.add(0, currentBlock); blockStart -= 4096; currentBlock = new byte[4096]; } } catch (Exception ex) { ex.printStackTrace(); } // oops, no line break found or some exception happened return ""; }
If you're worried about re-using this method. Might help to assure that I've authored this code snippet and that you are welcome to reuse this code under the MIT license terms. You are welcome to improve the code, there is certainly room for optimization.
Hope this helps.
:-)
Java: Writing lines in text files with a buffer
Text files are simple. The problem is when you need to write them a few million times.
A strange error from the file (or operating) system causes the Java Virtual Machine to crash when you keep adding data to a given file.
Quick solution was reducing the number of writes using a buffer to cache a number of text lines before writing the data on disk.
This way was possible to reduce the need for such frequent/numerous write operations.
You find the most up-to-date source code on GitHub at this link.
Not difficult to use, initialize the class with the file you want to write. Then use the write() method for each event you want to store and in the end call the close() method to finish any pending operations.
That's it. :-)
A strange error from the file (or operating) system causes the Java Virtual Machine to crash when you keep adding data to a given file.
Quick solution was reducing the number of writes using a buffer to cache a number of text lines before writing the data on disk.
This way was possible to reduce the need for such frequent/numerous write operations.
You find the most up-to-date source code on GitHub at this link.
Not difficult to use, initialize the class with the file you want to write. Then use the write() method for each event you want to store and in the end call the close() method to finish any pending operations.
That's it. :-)
Java: Reading millions of text lines at top speed
There is one thing to say about Java (as a platform), its performance while reading I/O from the disk using the default classes is impressive.
I'm sharing code to read as fast as possible the lines from a large-sized text file from disk and to process each line through a custom method.
The implementation is very simple, has no external dependencies. You find the code for download at this link on github.
btw. The above link will get you the most up-to-date version of the source code file.
Performance on my laptop (i7 CPU, 8Gb RAM, 500Gb HDD, Linux) is measured with a text file containing ~30 million lines of text (around 300 characters each) that is read under 2 minutes.
A practical example of the code in real-world is at this link. Basically, just copy the class to your project and then use "extends FileReadLines". Let the IDE create the needed methods and off you go to process each line or adapt the progress messages.
That's it.
While it is true that anyone can use bufferedReader on its own. The fact is that I found myself repeating these kind of things, therefore created a library to keep this code on a single location. Hope you find it useful if you're struggling to tackle large scaled flat-files.
To the best of my knowledge, this is the fastest possible way of reading a massive number of lines that uses nothing more than the Java platform.
If you have suggestions on how to reach faster results, please place them on the comments box and I'll update this post accordingly. My thanks in advance.
Also, feel free to change the code on GitHub as you see fit.
I'm sharing code to read as fast as possible the lines from a large-sized text file from disk and to process each line through a custom method.
btw. The above link will get you the most up-to-date version of the source code file.
Performance on my laptop (i7 CPU, 8Gb RAM, 500Gb HDD, Linux) is measured with a text file containing ~30 million lines of text (around 300 characters each) that is read under 2 minutes.
A practical example of the code in real-world is at this link. Basically, just copy the class to your project and then use "extends FileReadLines". Let the IDE create the needed methods and off you go to process each line or adapt the progress messages.
That's it.
While it is true that anyone can use bufferedReader on its own. The fact is that I found myself repeating these kind of things, therefore created a library to keep this code on a single location. Hope you find it useful if you're struggling to tackle large scaled flat-files.
To the best of my knowledge, this is the fastest possible way of reading a massive number of lines that uses nothing more than the Java platform.
If you have suggestions on how to reach faster results, please place them on the comments box and I'll update this post accordingly. My thanks in advance.
Also, feel free to change the code on GitHub as you see fit.
Looking into the .NET license compliance practice
This week Microsoft released to public the source code for the .NET platform. The code is published to the public at GitHub and released under the MIT license terms.
Better than just speaking about the advantages of open source, one should share their own code on the open sphere and this is when the licensing topic becomes a matter of scrutiny.
Now that this once proprietary code is now free and open to the public eye, I've took the liberty of looking inside the source to evaluate how well it would score in regards to licensing compliance.
To proceed with a licensing compliance check, I downloaded a copy of the source code and created a report using the triplecheck tool.
The result shows a project containing 630 files and 128 thousand lines of code. At the time of this evaluation, 534 files were identified with an MIT license reference, 540 files had reference to Microsoft as copyright holder. No other licenses were present.
The result is in the screenshot below.
I was happy to see how the current code base was almost reaching a 10/10 score. It was due to a few source code files that needed reference to author and applicable license that kept the 10 from reach.
Being hosted on GitHub means that it was straightforward to submit a bug report and the issue was picked up a few hours later by a developer.
On the second screenshot you see an overview of the code structure and what can be expected in regards to licensing.
The example highlights one of the files missing to correct.
This is a surface analysis, a deep analysis involves evaluating the code originality and the third-party dependencies. Please write a comment if you find a deeper analysis to be of interest and I'll proceed.
The report is available in the SPDX format by the Linux Foundation. You can view this document directly from a browser on this link at GitHub.
In conclusion, from a first week of releases to public it is clear that this code base demonstrates quality from a licensing perspective. Furthermore, the developer team is participative and transmits a notion of a serious commitment, which is much needed if the intention is to bridge the .NET platform with a healthy community spirit.
This is a sign of how the times are changing. And developing code open to public is certainly a good way to make these changes happen.
Better than just speaking about the advantages of open source, one should share their own code on the open sphere and this is when the licensing topic becomes a matter of scrutiny.
Now that this once proprietary code is now free and open to the public eye, I've took the liberty of looking inside the source to evaluate how well it would score in regards to licensing compliance.
To proceed with a licensing compliance check, I downloaded a copy of the source code and created a report using the triplecheck tool.
The result shows a project containing 630 files and 128 thousand lines of code. At the time of this evaluation, 534 files were identified with an MIT license reference, 540 files had reference to Microsoft as copyright holder. No other licenses were present.
The result is in the screenshot below.
I was happy to see how the current code base was almost reaching a 10/10 score. It was due to a few source code files that needed reference to author and applicable license that kept the 10 from reach.
Being hosted on GitHub means that it was straightforward to submit a bug report and the issue was picked up a few hours later by a developer.
On the second screenshot you see an overview of the code structure and what can be expected in regards to licensing.
The example highlights one of the files missing to correct.
This is a surface analysis, a deep analysis involves evaluating the code originality and the third-party dependencies. Please write a comment if you find a deeper analysis to be of interest and I'll proceed.
The report is available in the SPDX format by the Linux Foundation. You can view this document directly from a browser on this link at GitHub.
In conclusion, from a first week of releases to public it is clear that this code base demonstrates quality from a licensing perspective. Furthermore, the developer team is participative and transmits a notion of a serious commitment, which is much needed if the intention is to bridge the .NET platform with a healthy community spirit.
This is a sign of how the times are changing. And developing code open to public is certainly a good way to make these changes happen.
Simple way to order an ArrayList in Java
Often in Java one ends up using ArrayLists to store objects.
Every now and then becomes needed to sort the elements inside an array, either in descending or ascending order according to some attribute of the object.
This is a somewhat tricky operation that gets forgotten too often, therefore I'm documenting it for future reference to myself. Much of what is written here was based on the tutorial from Mkyong: http://www.mkyong.com/java/java-object-sorting-example-comparable-and-comparator/
First step:
Make the object that you want to order to extend the "Comparable" class.
On my case, I want to apply the ordering on the SourceCodeObject class, so I add the line:
implements Comparable<SourceCodeFile>
And it looks like this:
https://github.com/triplecheck/f2f/blob/26db102366be6b1eaeae2fcbb8bb0e966d951d6a/src/structure/SourceCodeFile.java#L25
Second step:
Override the "compareTo" method. On this case the comparison can occur between any two attributes of the objects that you are comparing. I find it difficult to understand in detail how it works. For my case it was enough to subtract two values and return the value. You find the code example at:
https://github.com/triplecheck/f2f/blob/26db102366be6b1eaeae2fcbb8bb0e966d951d6a/src/structure/SourceCodeFile.java#L150-L153
Third step:
Convert the ArrayList to an array and then sort the array. This is the part that I find tricky because the syntax to convert the ArrayList to a plain array is not straightforward to understand, even from the help menu.
It should be something like:
SourceCodeFile[] array = myArrayList.toArray(new SourceCodeFile[myArrayList.size()]);
Arrays.sort(array);
You find the code example at:
https://github.com/triplecheck/f2f/blob/26db102366be6b1eaeae2fcbb8bb0e966d951d6a/src/structure/AnalysisResult.java#L223-L225
That's it. Enjoy the sorted array!
In resume:
- Add the "Comparable" class to the object you want to compare
- Add the "toCompare" method
- Apply the Arrays.sort for ordering the items on a new array.
Simpler ways?
This method worked for me and I found it ok. Surely other ways exist. What do you think? How would you have implemented ordering?
This is a somewhat tricky operation that gets forgotten too often, therefore I'm documenting it for future reference to myself. Much of what is written here was based on the tutorial from Mkyong: http://www.mkyong.com/java/java-object-sorting-example-comparable-and-comparator/
First step:
Make the object that you want to order to extend the "Comparable" class.
On my case, I want to apply the ordering on the SourceCodeObject class, so I add the line:
implements Comparable<SourceCodeFile>
And it looks like this:
https://github.com/triplecheck/f2f/blob/26db102366be6b1eaeae2fcbb8bb0e966d951d6a/src/structure/SourceCodeFile.java#L25
Second step:
Override the "compareTo" method. On this case the comparison can occur between any two attributes of the objects that you are comparing. I find it difficult to understand in detail how it works. For my case it was enough to subtract two values and return the value. You find the code example at:
https://github.com/triplecheck/f2f/blob/26db102366be6b1eaeae2fcbb8bb0e966d951d6a/src/structure/SourceCodeFile.java#L150-L153
Third step:
Convert the ArrayList to an array and then sort the array. This is the part that I find tricky because the syntax to convert the ArrayList to a plain array is not straightforward to understand, even from the help menu.
It should be something like:
SourceCodeFile[] array = myArrayList.toArray(new SourceCodeFile[myArrayList.size()]);
Arrays.sort(array);
You find the code example at:
https://github.com/triplecheck/f2f/blob/26db102366be6b1eaeae2fcbb8bb0e966d951d6a/src/structure/AnalysisResult.java#L223-L225
That's it. Enjoy the sorted array!
In resume:
- Add the "Comparable" class to the object you want to compare
- Add the "toCompare" method
- Apply the Arrays.sort for ordering the items on a new array.
Simpler ways?
This method worked for me and I found it ok. Surely other ways exist. What do you think? How would you have implemented ordering?
Using a simple memory cache to speed-up disk operations
A new cycle of work has now debuted on the F2F project.
In the first version I was going through a bigzip file containing some 30 million Java source code files to convert the code into tokens.
However, the conversion tool had no support to stop/resume the processing. This meant that it would require running the same process 24/7 without any interruptions to complete the task. At the time I was working under a tight schedule and used only a sub-set of the data with some 4 million source code files.
Now, there is time and the tool needs to go through these millions of source code files, being ready to resume the processing in case something goes wrong is a needed feature.
On the first version I'd basically read the contents of a source code file, convert the content into a set of tokens and then write them back on a destination file.
To add a stop/resume feature, one needs to "persist" the memory on disk of the last data which was recorded, in order to know from where to begin on the next re-start. Writing a file to disk doesn't scale under this stress. After some hundred thousands writes it will output "JVM error". This also wears down the HDD.
Another option I tried was MapDB, which is great for persistency with just a few lines of code. However, when calling MapDB to create a checkpoint on file-by-file basis this ended up reducing the performance from 4.000 files/minute to 300 files/minute. Clearly, this would make it difficult to index the whole millions of source code files before 2015.
Writing a single line of text on a file is a bottleneck, even if the line is relatively small.
A very simple solution to this problem was adding a memory cache.
Basically, set a normal string to hold the contents of 1000 token files to be written. Once that threshold is reached, the whole text is written back into the destination file just a single time, instead of 1000.
This simple measure has not only permitted to introduce the checkpoints with MapDB to record the current processing status, as it ended up speeding the process rate to ~16.000 files/minute. Really fast, just wow. I'm still mesmerized by the output speed, some 3 millions already reached in a few hours. The whole set should be converted by tomorrow night.
The tradeoff is memory usage. Some barriers were already in place to avoid processing large sized source code files but let's see how this cache holds on.
You find the relevant code snippet here.
:-)
In the first version I was going through a bigzip file containing some 30 million Java source code files to convert the code into tokens.
However, the conversion tool had no support to stop/resume the processing. This meant that it would require running the same process 24/7 without any interruptions to complete the task. At the time I was working under a tight schedule and used only a sub-set of the data with some 4 million source code files.
On the first version I'd basically read the contents of a source code file, convert the content into a set of tokens and then write them back on a destination file.
To add a stop/resume feature, one needs to "persist" the memory on disk of the last data which was recorded, in order to know from where to begin on the next re-start. Writing a file to disk doesn't scale under this stress. After some hundred thousands writes it will output "JVM error". This also wears down the HDD.
Another option I tried was MapDB, which is great for persistency with just a few lines of code. However, when calling MapDB to create a checkpoint on file-by-file basis this ended up reducing the performance from 4.000 files/minute to 300 files/minute. Clearly, this would make it difficult to index the whole millions of source code files before 2015.
Writing a single line of text on a file is a bottleneck, even if the line is relatively small.
A very simple solution to this problem was adding a memory cache.
Basically, set a normal string to hold the contents of 1000 token files to be written. Once that threshold is reached, the whole text is written back into the destination file just a single time, instead of 1000.
This simple measure has not only permitted to introduce the checkpoints with MapDB to record the current processing status, as it ended up speeding the process rate to ~16.000 files/minute. Really fast, just wow. I'm still mesmerized by the output speed, some 3 millions already reached in a few hours. The whole set should be converted by tomorrow night.
The tradeoff is memory usage. Some barriers were already in place to avoid processing large sized source code files but let's see how this cache holds on.
You find the relevant code snippet here.
:-)
First pull request on GitHub
Since a year to this part that I've been using increasingly more GitHub for everything related to source code hosting.
My impression with them has been very positive since the start. From the web interface that is straightforward, to the social "gamification" in place that motivates developers to commit code more often and to see how they are doing.
Another thing that got me surprised was the availability of a direct API to extract all kind of data from the platform with very little limitations, as if it was your own data to download. This revealed something very deep, that the site was made by developers for developers and that sharing was a keyword taken to practice.
Yesterday I got surprised, once again. Was looking around some code that I found interesting and ended up suggesting some minor improvements. A few days later got a message from the author, a github staff asking if I could do "pull request": https://github.com/benbalter/peer_review/pull/2#event-169874904
It was the first I had to deal with this kind of request. Was feeling a bit lost but he took the time to help me get around. How often do you get someone from the GitHub staff helping you directly to get code shared?
Yep. This is the kind of attitude that makes a platform living and thriving. Great people.
Thumbs up to GitHub.
My impression with them has been very positive since the start. From the web interface that is straightforward, to the social "gamification" in place that motivates developers to commit code more often and to see how they are doing.Another thing that got me surprised was the availability of a direct API to extract all kind of data from the platform with very little limitations, as if it was your own data to download. This revealed something very deep, that the site was made by developers for developers and that sharing was a keyword taken to practice.
Yesterday I got surprised, once again. Was looking around some code that I found interesting and ended up suggesting some minor improvements. A few days later got a message from the author, a github staff asking if I could do "pull request": https://github.com/benbalter/peer_review/pull/2#event-169874904
It was the first I had to deal with this kind of request. Was feeling a bit lost but he took the time to help me get around. How often do you get someone from the GitHub staff helping you directly to get code shared?
Yep. This is the kind of attitude that makes a platform living and thriving. Great people.
Thumbs up to GitHub.
Quem não tem cão, caça com gato.
I've noted that each month has been entertaining but this one (August) is passing over the "busyness" level.
Some months ago we set as goal to prepare the company for the processing of open source code in a larger scale. It was no longer enough to just develop the tooling for discovery and marking the licenses of open source files, we now required our own knowledge base to improve the detection techniques.
To make this possible, we would then require an infrastructure capable of handling files in larger scale. "You need hadoop" they said. But our resources are scarce. The company income is barely enough to cover a salary. Scaling our technology reach to tackle millions of files seemed a long shot when considering what we have at hand.
But it wasn't.
I remember with a smile the Portuguese proverb: "Quem não tem cão, caça com gato" (in English: Those without a dog, hunt with a cat). And so was the case.
No money for server farms. No Amazon cloud processing, no distributed storage. No teams of engineers, scientists and mathematicians using Hadoop and other big data buzz. No time for peer review nor academic research. No public funding.
And perhaps it was better this way.
It is a lonely and daunting task to write something that involves parallel operations, files with hundreds of gigabytes and an ever closer deadline to deliver a working solution.
However, it does force a person to find a way through the mess. To look at what really matters, to simply say "no" and keep focus. It is a lonely task but at the same time you're left to decide without delay. To experiment without fear and motivated for each day getting a bit closer to the intended goal.
So was the case. What seemed difficult for a single person to implement, was split into pieces that together built an infrastructure. I always keep close to mind the wise saying by a professor at CMU: "You don't know what you don't know". Too often the working solution differed from the planned solution. Very true indeed!
To some point I'm happy. We got things working very fast with a simplicity that anyone can maintain. Several hundred millions files processed in a month, over a hundred million stored in our archive and now moving to the final stage at fast pace.
Turned up that we didn't needed a large team, nor a computer farm, nor the full stack of big data buzz. Surely they are relevant. Surely in our case they were non-affordable, simpler solutions got things working.
TL;DR:
If a big data challenge can be broken into smaller pieces, go for it.
Some months ago we set as goal to prepare the company for the processing of open source code in a larger scale. It was no longer enough to just develop the tooling for discovery and marking the licenses of open source files, we now required our own knowledge base to improve the detection techniques.
But it wasn't.
I remember with a smile the Portuguese proverb: "Quem não tem cão, caça com gato" (in English: Those without a dog, hunt with a cat). And so was the case.
No money for server farms. No Amazon cloud processing, no distributed storage. No teams of engineers, scientists and mathematicians using Hadoop and other big data buzz. No time for peer review nor academic research. No public funding.
And perhaps it was better this way.
It is a lonely and daunting task to write something that involves parallel operations, files with hundreds of gigabytes and an ever closer deadline to deliver a working solution.
However, it does force a person to find a way through the mess. To look at what really matters, to simply say "no" and keep focus. It is a lonely task but at the same time you're left to decide without delay. To experiment without fear and motivated for each day getting a bit closer to the intended goal.
So was the case. What seemed difficult for a single person to implement, was split into pieces that together built an infrastructure. I always keep close to mind the wise saying by a professor at CMU: "You don't know what you don't know". Too often the working solution differed from the planned solution. Very true indeed!
To some point I'm happy. We got things working very fast with a simplicity that anyone can maintain. Several hundred millions files processed in a month, over a hundred million stored in our archive and now moving to the final stage at fast pace.
Turned up that we didn't needed a large team, nor a computer farm, nor the full stack of big data buzz. Surely they are relevant. Surely in our case they were non-affordable, simpler solutions got things working.
TL;DR:
If a big data challenge can be broken into smaller pieces, go for it.
The hidden overhead when creating thousands of empty folders
Over the past weeks I've been looking for a way to store some hundred million files inside a desktop file system such as Ext3 or NTFS.
On previous experiments, I've noted that after >30 000 files on a single folder it would not be possible to use a GUI file browser and even the listing of these files using the command line becomes sluggish.
The next hypothesis was to avoid a huge number of files/folders on the same root. For example, for a file I'd remove the name portion and compute a SHA1 checksum signature of 40 bytes. With this signature I'd use the first 4 bytes to create a folder, then I'd use the next 4 bytes to create a sub-folder inside the first one and so forth until I have 10 folders that represent the unique signature of the file.
On the last folder I would add a text file containing the path and name information. If more files would be found in the future, the respective path information would be added on this text file. I thought that using the 4 bytes would reduce the number of possible combinations and permit re-use of the folders that would scale to millions.
In theory it worked OK. On my first tests it worked OK with the first thousand files. The problem was a bit more unexpected. Folders, despite containing nothing other than other folders will also require disk space to exist. While the initial project was a success, we could store/access thousands of files without noticeable latency, we brought aboard a problem of disk storage.
To index something like 40 000 files with this SHA1/folder combination was using 2.2Gb of disk space. This was a hidden overhead, very underestimated on my early estimation.
I didn't tested under the Windows NTFS, having this problem under Linux was already a no-go for this option. Fortunately, on the bench was already being planned an alternative.
Our file-system (at minimum) requires only to write files once and then read them when needed. So, a very simple solution would be writing all files together to create a very large file. And then have a second file indicating the position of each file within this large binary block.
There are some problems with this approach:
As far as I'm concerned, creating millions of files on a desktop-grade file system is something I won't be pursuing further. It is tempting to have all the files ready for processing in their original format but I'm simply not finding a feasible manner of accessing millions of files in their original form without resorting to file systems such as XFS and HDFS, or resorting to some kind of data base.
So, opting with a big-binary file as simple storage for now.
The next hypothesis was to avoid a huge number of files/folders on the same root. For example, for a file I'd remove the name portion and compute a SHA1 checksum signature of 40 bytes. With this signature I'd use the first 4 bytes to create a folder, then I'd use the next 4 bytes to create a sub-folder inside the first one and so forth until I have 10 folders that represent the unique signature of the file.
On the last folder I would add a text file containing the path and name information. If more files would be found in the future, the respective path information would be added on this text file. I thought that using the 4 bytes would reduce the number of possible combinations and permit re-use of the folders that would scale to millions.
In theory it worked OK. On my first tests it worked OK with the first thousand files. The problem was a bit more unexpected. Folders, despite containing nothing other than other folders will also require disk space to exist. While the initial project was a success, we could store/access thousands of files without noticeable latency, we brought aboard a problem of disk storage.
To index something like 40 000 files with this SHA1/folder combination was using 2.2Gb of disk space. This was a hidden overhead, very underestimated on my early estimation.
I didn't tested under the Windows NTFS, having this problem under Linux was already a no-go for this option. Fortunately, on the bench was already being planned an alternative.
Our file-system (at minimum) requires only to write files once and then read them when needed. So, a very simple solution would be writing all files together to create a very large file. And then have a second file indicating the position of each file within this large binary block.
There are some problems with this approach:
- Easy to corrupt. If one byte within the large block is removed/added then it invalidates the index structure completely
- Error checking overhead. Right now it copies files directly onto the big binary block (BBB). If an exception occurs while copying a file, this leads to corruption of the whole big file.
- Limited to operating systems capable of handling files bigger than 4Gb
- (..more exist, just pointing the ones most troublesome at the moment)
As far as I'm concerned, creating millions of files on a desktop-grade file system is something I won't be pursuing further. It is tempting to have all the files ready for processing in their original format but I'm simply not finding a feasible manner of accessing millions of files in their original form without resorting to file systems such as XFS and HDFS, or resorting to some kind of data base.
So, opting with a big-binary file as simple storage for now.
GitHub: Indexing all users non-stop
Last week was dedicated to index the users registered on GitHub.
Getting the users was a needed step in order to test how difficult it would be extracting information from the self-appointed largest (public) open source repository on earth.
To my surprise, it was relatively straight-forward and quick. Over the past months I've understood why GitHub is becoming the place of election for hosting. It was a neat user interface, provides incentives for developers to commit code and simply goes straight to what really matters.
In regards to acessing the information, GitHub provides a pretty amazing and reachable API access. When looking at sourceforge or googlecode, I don't fell minimally invited to work with them in regards to analyse the open source data. I'm sure they have their valid reasons, on my side I'm just looking for a straightforward (and legal) way to access this kind of information.
To access the API was available a set of Java libraries (or you can just use the raw JSON format). There is JCapi (freeware) which is the one that I found more suited. The reason is because every now and then we'd expire the API rate limit (5000 requests/hour) and these libraries permitted to keep the connection in pause until the limit was lifted. There were some defects noted while using the library, however, the developers behind the library were pretty amazing. They solved most of the reported issues in light-speed.
With the library in place, I've wrote a java project to iterate through all the users registered on GitHub using the authorized API calls. At first was noted that the Internet connection broke very often, usually around 200k indexed users. I was doing these tests from the office network and was not stable enough. Then moved the software to a dedicated server that is continuously online at a datacenter. From there the connection lasted longer but still failed at 800k indexed users.
Being a stubborn person by nature, got myself thinking on how to resume the operation from the point where it had stopped. The API did provided a resume option from a given user name but the libraries didn't yet covered this point, to my luck the jcabi team was very prompt in explaining how the API call could be used. With the support for resuming available, was then a simple matter to read back the text file with each user per line and get the last one.
Didn't said it before but the storage media that I'm using are plain text files (a.k.a flat files). I'm not using a relational database, nor have I looked much into "NoSQL" databases. From all the options that I've tested over the years, nothings beats the processing simplicity of a plain text file to store large arrays of data. Please note that I emphasize simplicity. If performance had been affected significantly, I'd use a more suited method. However, turns out that normal desktop computers in 2014 can handle text files with millions of lines under a second.
With the resume feature implemented was then possible to launch a single machine for indexing the user names non-stop. After two days of processing, the indexing was complete and showed a total of 7.709.288 registered users.
At the time of this writing (July 2014), GitHub mentions in their press page a total of 6 million users. The text file containing these user names is sized in 81Mb. It contains one user name per line.
Perhaps in the future would be interesting to see a study noting the demographics, gender variation and other details from these user accounts. On my context, this is part of a triplecheck goal. Open source is open, but is not transparent enough. And that is what we are working to improve.
Following the spirit of open source and free software, the software used for generating this index of users is too available on github. It is released as freeware under the modified EUPL (European Public Licence) terms. You find the code and compilation instructions at https://github.com/triplecheck/gitfinder
This code does more than just indexing users, I'll be writing more about what is being done in future posts. In the meanwhile you might be asking yourself: where can I get this text file?
For the moment I didn't made the text file available on a definitive location. Will likely talk with the good people at FLOSSmole to see if they would be interested in hosting and keeping it easily reachable to other folks.
Forward we move.
:-)
Getting the users was a needed step in order to test how difficult it would be extracting information from the self-appointed largest (public) open source repository on earth.
To my surprise, it was relatively straight-forward and quick. Over the past months I've understood why GitHub is becoming the place of election for hosting. It was a neat user interface, provides incentives for developers to commit code and simply goes straight to what really matters.
To access the API was available a set of Java libraries (or you can just use the raw JSON format). There is JCapi (freeware) which is the one that I found more suited. The reason is because every now and then we'd expire the API rate limit (5000 requests/hour) and these libraries permitted to keep the connection in pause until the limit was lifted. There were some defects noted while using the library, however, the developers behind the library were pretty amazing. They solved most of the reported issues in light-speed.
With the library in place, I've wrote a java project to iterate through all the users registered on GitHub using the authorized API calls. At first was noted that the Internet connection broke very often, usually around 200k indexed users. I was doing these tests from the office network and was not stable enough. Then moved the software to a dedicated server that is continuously online at a datacenter. From there the connection lasted longer but still failed at 800k indexed users.
Being a stubborn person by nature, got myself thinking on how to resume the operation from the point where it had stopped. The API did provided a resume option from a given user name but the libraries didn't yet covered this point, to my luck the jcabi team was very prompt in explaining how the API call could be used. With the support for resuming available, was then a simple matter to read back the text file with each user per line and get the last one.
Didn't said it before but the storage media that I'm using are plain text files (a.k.a flat files). I'm not using a relational database, nor have I looked much into "NoSQL" databases. From all the options that I've tested over the years, nothings beats the processing simplicity of a plain text file to store large arrays of data. Please note that I emphasize simplicity. If performance had been affected significantly, I'd use a more suited method. However, turns out that normal desktop computers in 2014 can handle text files with millions of lines under a second.
With the resume feature implemented was then possible to launch a single machine for indexing the user names non-stop. After two days of processing, the indexing was complete and showed a total of 7.709.288 registered users.
At the time of this writing (July 2014), GitHub mentions in their press page a total of 6 million users. The text file containing these user names is sized in 81Mb. It contains one user name per line.
Perhaps in the future would be interesting to see a study noting the demographics, gender variation and other details from these user accounts. On my context, this is part of a triplecheck goal. Open source is open, but is not transparent enough. And that is what we are working to improve.
Following the spirit of open source and free software, the software used for generating this index of users is too available on github. It is released as freeware under the modified EUPL (European Public Licence) terms. You find the code and compilation instructions at https://github.com/triplecheck/gitfinder
This code does more than just indexing users, I'll be writing more about what is being done in future posts. In the meanwhile you might be asking yourself: where can I get this text file?
For the moment I didn't made the text file available on a definitive location. Will likely talk with the good people at FLOSSmole to see if they would be interested in hosting and keeping it easily reachable to other folks.
Forward we move.
:-)
Java: Parsing text files with minimum delay
In this blog post I'm gathering some of the things that I've learned from practice while making my own code process faster a significant amount of lines inside a text file.
In the most recent work I'm parsing 440 000 lines inside a text file under a second. My hardware is nothing special for today's standards, it is a Toshiba R630, a x64 CPU with 4Gb of RAM running Windows 7.
The result can currently be seen on https://github.com/triplecheck/reporter/blob/b5ca1781dc511b3a823724606a07d7fc61e1d9e3/src/spdxlib/SPDXfile2.java#L197 on the method processFileLine. The link might change in the future, so please do write back a message in case I don't update the above link.
During this parsing, quite a number of time consuming tasks take place:
- Discovering the type of file extension (is it a source code file? an image? an archive? ...)
- What kind of line are we reading (a checksum line? the file size? the license details? the next file? ...)
- Creating a node to place the current file on a treeview under a specific folder
All in all, the first edition worked fairly for smaller text files but failed at reports that contained thousands of lines. Either the memory wouldn't be enough (not enough heap size) or it would just be too slow (for example, generating the treeview was real slow). There was a serious effort to merge the number of loops onto a single loop and to drastically reduce the calculation and filtering time. I've started with first testing different ways of reading all files one by one and BufferedReader came as the fastest option.
Then, step by step I'd introduce a new value being parsed and test the performance to see how it would be degraded and try to optimize. The end result was satisfactory and below are some of my field notes that I kept around for future memory. It is not an exhaustive nor correct list of things you should/can do. It worked for my own goals and it is my hope it can somehow be useful for you too.
If you know any further optimizations that can take place, I'd be happy to include them here and assign proper credits.
There is a dramatic speed-up boost when looking for a char inside a string. Here is a working example:
In the past, perhaps due to dislike for nested IF's, I overlooked the simple fact that they should be nested with an "IF ELSE, IF ELSE, IF..." format. This is important. Once a condition is matched, the other IF statements shouldn't matter.
How to convert from a piece of String to Enum?
Use the .valueOf("sometext") method that available by default on Enums. This turned out to be very efficient converting the set of possible values onto an enum that we can process.
Here is practical example where I get the value from a text line and then place it directly inside an object that expects an enum. If you note, I have no error checking present:
What happens when data has a problem? Things fail. There is an exception to be caught and that should be the only safety net that you have around for ensuring that you can process the data. Thinking about our own context, this made sense. For large text files, most of the effort is automated by tooling and not so much by humans. If something is wrong in the file, this should cause quite a fuss in order to be corrected.
The end result is a performance boost since we removed the need for so many IFs: "Is the text different from null? Is the value an integer? ...". Trust the data.
This is valid not just for strings but rather for any object out there.
Wasn't easy at first (a lot of the code had to be rewritten) but guess what? The code previously taking some 8 seconds to compute the treeview paths now takes less than a second. One big loop forces code to be simpler, helps to note immediately if loading performance is degrading somewhere.
If it is not recommendable to delete the source code file, consider moving into the "old" folder where it can be retrieved if/when necessary.
In the most recent work I'm parsing 440 000 lines inside a text file under a second. My hardware is nothing special for today's standards, it is a Toshiba R630, a x64 CPU with 4Gb of RAM running Windows 7.
The result can currently be seen on https://github.com/triplecheck/reporter/blob/b5ca1781dc511b3a823724606a07d7fc61e1d9e3/src/spdxlib/SPDXfile2.java#L197 on the method processFileLine. The link might change in the future, so please do write back a message in case I don't update the above link.
During this parsing, quite a number of time consuming tasks take place:
- Discovering the type of file extension (is it a source code file? an image? an archive? ...)
- What kind of line are we reading (a checksum line? the file size? the license details? the next file? ...)
- Creating a node to place the current file on a treeview under a specific folder
All in all, the first edition worked fairly for smaller text files but failed at reports that contained thousands of lines. Either the memory wouldn't be enough (not enough heap size) or it would just be too slow (for example, generating the treeview was real slow). There was a serious effort to merge the number of loops onto a single loop and to drastically reduce the calculation and filtering time. I've started with first testing different ways of reading all files one by one and BufferedReader came as the fastest option.
Then, step by step I'd introduce a new value being parsed and test the performance to see how it would be degraded and try to optimize. The end result was satisfactory and below are some of my field notes that I kept around for future memory. It is not an exhaustive nor correct list of things you should/can do. It worked for my own goals and it is my hope it can somehow be useful for you too.
If you know any further optimizations that can take place, I'd be happy to include them here and assign proper credits.
Compiler not compiling
The Java compiler is not perfect. Just because it seems to always do a good work, there are some (rare) cases where you will need ask for a general re-compiling of all the classes. This has sometimes worked to address strange behaviors on the code that I was having trouble to figure until a full compilation was asked.ASCII: party like it's 1998
One significant code speed-up happened after going back to compare characters instead of strings. There is a heavy performance cost when comparing strings but I guess nowadays machines have grown so fast that it gets easy not caring and just compare strings. When looking for performance, it is needed to go back into the days where an ASCII table was always present (if you didn't knew the ASCII codes by memory like Mr. Bill Gates once said he did). So, back to the 90's and looking online at places like http://www.asciitable.com/ to get refreshed with the chars codes.There is a dramatic speed-up boost when looking for a char inside a string. Here is a working example:
// find the "(" char which is represented by "40" in ASCII
final int index = value.indexOf(40);
if(index==-1){
// do your code here
}
Nested IF's
I'm not a friend of spaghetti code. However, from my experiments was possible to note that nested IF's can help to improve performance too. On my context, I was reading a large text file line by line and trying to recognize tags. This required quite a number of IF's.In the past, perhaps due to dislike for nested IF's, I overlooked the simple fact that they should be nested with an "IF ELSE, IF ELSE, IF..." format. This is important. Once a condition is matched, the other IF statements shouldn't matter.
Breaking large code into smaller methods
I have no scientific evidence for this recommendation but besides the advantage of making a large method easier to read, I've noted that when moving a piece of code onto its own method that I'd get a slight performance boost. It is my impression that the compiler is better prepared to optimize smaller methods than large ones.ENUM, ENUM
When possible, use and abuse of ENUMS. A comparison between Enums is faster than comparing strings. In the past I've neglected too often this kind of performance magic, simply because it was easy to compare strings, even when using statically defined strings. Looking into the code, I've replaced everything where possible with an Enum. Whenever the value for a given object would only fall into a couple of categories, enum you become.How to convert from a piece of String to Enum?
Use the .valueOf("sometext") method that available by default on Enums. This turned out to be very efficient converting the set of possible values onto an enum that we can process.
Here is practical example where I get the value from a text line and then place it directly inside an object that expects an enum. If you note, I have no error checking present:
final String temp = tagGetValue(is.tagFileType, line);
tempInfo.setFileType(FileCategory.valueOf(temp));
Trust the data
Another thing that I always tried to do is preventing errors from happening. I placed quite an effort in detecting if a given piece of data was within a set of restrictions before being used. For performance, I can't afford to do these checks. You have to trust that the data being provided can be fed directly onto the object.What happens when data has a problem? Things fail. There is an exception to be caught and that should be the only safety net that you have around for ensuring that you can process the data. Thinking about our own context, this made sense. For large text files, most of the effort is automated by tooling and not so much by humans. If something is wrong in the file, this should cause quite a fuss in order to be corrected.
The end result is a performance boost since we removed the need for so many IFs: "Is the text different from null? Is the value an integer? ...". Trust the data.
The Final countdown
I never realized how using "Final" for strings could have such an impact on performance. Only now understood how this tells the compiler: "This string doesn't chance EVER AGAIN", which in return blessed the program execution with a whooping speed boost. I'm unable of explaining the intricacies behind this mystery but is something that I'm now using with good results.This is valid not just for strings but rather for any object out there.
GPU vs CPU
I've considered the usage of GPU (processing through graphic cards). This is wonderful for speeding up the computation but then noted that my own code needed to be optimized and throwing more hardware power at the problem wouldn't really be a solution. Our machines are so much more powerful than most servers back in the 90's. Somehow they managed to get things done efficiently, so must we.One big loop to rule them all
When looking again into the working code I noted too many loops. There was one to find all files, another to place them on a treeview and sometimes a full loop for each time, resulting in exponential calculations that were not really efficient. So, decided to use a single loop. No excuses, just one big loop to do all the math for each file item.Wasn't easy at first (a lot of the code had to be rewritten) but guess what? The code previously taking some 8 seconds to compute the treeview paths now takes less than a second. One big loop forces code to be simpler, helps to note immediately if loading performance is degrading somewhere.
Keep strings small
Another thing that helped was keeping the size of strings to be compared as minimally small as possible. Avoid a full string text search, do instead a search that starts from the beginning of the text, up to a specific number of characters.Code will be deleted
The side effect of optimizing code is removing a lot of the fat existing before. The hardest part is actually deleting source code files because it kind of raises an alarm. From a psychological point of view, deleting files means losing code. I guess it is counter-intuitive that when an application get better by removing code, it just feels wrong to delete old files. Not easy, but a clean-up needs to be done.If it is not recommendable to delete the source code file, consider moving into the "old" folder where it can be retrieved if/when necessary.
Leverage the knowledge of others
My thanks to Michael Schierl the extra tip added on this post. In his comment Michael brings up the advantage of using tools and frameworks already available to help profile performance. I quote and agree with his comment:There are lots of code style and performance checking tools available (PMD, CheckStyle, FindBugs) - run them on your code and have a look at least at the "high priority" issues.
If you are too lazy to set up multiple tools and wade through multiple reports, get the free edition of SonarQube, add all free Java analysis plugins you can find, and let it analyze your code, then look at the resulting report. (In case you are using CI like Hudson or Jenkins - most likely for larger projects or commercial ones - add a SonarQube job to it - SonarQube has ways to filter "new violations" - even by committer - if run often enough, so that you don't have to look at the same issues every time.
Java: catch (Exception e) does not catch all exceptions..
Today I was testing a piece of code that resulted in exception. The result from the exception was output to screen.
I've placed the normal "try..catch" block to control the exception but it was stubborn. Completely ignored the generic exception and kept on moving along its way.
After some research on this strange phenomenon, it turns that the "catch-all" (Exception e) is not catching "everything" when an exception occurs. The explanation came from this other blog post at http://10kloc.wordpress.com/2013/03/09/runtimeexceptions-try-catch-or-not-to-catch/
There is another class of exceptions called "RuntimeException".
When replacing "Exception" with "RuntimeException" then I was able to regain control of the exception handling and get more details about why it was happening.
Well, mystery solved.
I've placed the normal "try..catch" block to control the exception but it was stubborn. Completely ignored the generic exception and kept on moving along its way.
After some research on this strange phenomenon, it turns that the "catch-all" (Exception e) is not catching "everything" when an exception occurs. The explanation came from this other blog post at http://10kloc.wordpress.com/2013/03/09/runtimeexceptions-try-catch-or-not-to-catch/
There is another class of exceptions called "RuntimeException".
When replacing "Exception" with "RuntimeException" then I was able to regain control of the exception handling and get more details about why it was happening.
Well, mystery solved.
Subscribe to:
Posts (Atom)
